 Author
 Year
 2005
 Title
 Integer decomposition for polyhedra defined by nearly totally unimodular matrices.
 Journal
 SIAM Journal on Discrete Mathematics
 Volume  Issue number
 19  3
 Number of pages
 9
 Document type
 Article
 Faculty
 Faculty of Science (FNWI)
 Institute
 Kortewegde Vries Institute for Mathematics (KdVI)
 Abstract

Abstract. We call a matrix $A$ nearly totally unimodular if it can be obtained from a totally unimodular matrix $\tilde{A}$ by adding to each row of $\tilde{A}$ an integer multiple of some fixed row $a^{\transp}$ of $\tilde{A}$. For an integer vector $b$ and a nearly totally unimodular matrix $A$, we denote by $P_{A,b}$ the integer hull of the set $\{x\in\mathbb{R}^n\mid Ax\leq b\}$. We show that $P_{A,b}$ has the integer decomposition property and that we can find a decomposition of a given integer vector $x\in kP_{A,b}$ in polynomial time.
An interesting special case that plays a role in many cyclic scheduling problems is when $A$ is a circularones matrix. In this case, we show that given a nonnegative integer $k$ and an integer vector $x$, testing if $x\in kP_{A,b}$ and finding a decomposition of $x$ into $k$ integer vectors in $P_{A,b}$ can be done in time $O(n(n+m)+\text{size}(x))$, where $A$ is an $m\times n$ matrix. We show that the method unifies some known results on coloring circular arc graphs and edge coloring nearly bipartite graphs. It also gives an efficient algorithm for a packet scheduling problem for smart antennas posed by Amaldi, Capone, and Malucelli in [Fourth ALIO/EURO Workshop on Applied Combinatorial Optimization, Pucón, Chile, 2002]; [Proceedings of the Second CologneTwente Workshop on Graphs and Combinatorial Optimization, Vol. 1, 2003, pp. 14].
Key words. integer decomposition, totally unimodular, circular arc graph, nearly bipartite graph, cyclic scheduling, coloring
AMS Subject Classifications. 90C10 , 05C15 , 05C70  URL
 go to publisher's site
 Language
 Undefined/Unknown
 Permalink
 http://hdl.handle.net/11245/1.249129
Disclaimer/Complaints regulations
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.