2004 | OriginalPaper | Buchkapitel
Integer Concave Cocirculations and Honeycombs
verfasst von : Alexander V. Karzanov
Erschienen in: Integer Programming and Combinatorial Optimization
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
A convex triangular grid is a planar digraph G embedded in the plane so that each bounded face is an equilateral triangle with three edges and their union ${\cal R}$ forms a convex polygon. A function $h:E(G)\to{\mathbb R}$ is called a concave cocirculation if h(e)=g(v)–g(u) for each edge e=(u,v), where g is a concave function on ${\cal R}$ which is affinely linear within each bounded face of G. Knutson and Tao obtained an integrality result on so-called honeycombs implying that if an integer-valued function on the boundary edges is extendable to a concave cocirculation, then it is extendable to an integer one.We show a sharper property: for any concave cocirculation h, there exists an integer concave cocirculation h′ satisfying h′(e)=h(e) for each edge e with $h(e)\in{\mathbb Z}$ contained in the boundary or in a bounded face where h is integer on all edges.Also relevant polyhedral and algorithmic results are presented.