Traversing combinatorial 0/1-polytopes via optimization

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F23%3A10476060" target="_blank" >RIV/00216208:11320/23:10476060 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1109/FOCS57990.2023.00076" target="_blank" >https://doi.org/10.1109/FOCS57990.2023.00076</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1109/FOCS57990.2023.00076" target="_blank" >10.1109/FOCS57990.2023.00076</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Traversing combinatorial 0/1-polytopes via optimization

Popis výsledku v původním jazyce

In this paper, we present a new framework that exploits combinatorial optimization for efficiently generating a large variety of combinatorial objects based on graphs, matroids, posets and polytopes. Our method relies on a simple and versatile algorithm for computing a Hamilton path on the skeleton of any 0/1-polytope conv(X), where X is a subset of  {0,1}^n. The algorithm uses as a black box any algorithm that solves a variant of the classical linear optimization problem min {w . x ; x is from X}, and the resulting delay, i.e., the running time per visited vertex on the Hamilton path, is only by a factor of log n larger than the running time of the optimization algorithm. When X encodes a particular class of combinatorial objects, then traversing the skeleton of the polytope conv(X) along a Hamilton path corresponds to listing the combinatorial objects by local change operations, i.e., we obtain Gray code listings. As concrete results of our general framework, we obtain efficient algorithms for generating all (c-optimal) bases and independent sets in a matroid; (c-optimal) spanning trees, forests, matchings, maximum matchings, and c-optimal matchings in a general graph; vertex covers, minimum vertex covers, c-optimal vertex covers, stable sets, maximum stable sets and c-optimal stable sets in a bipartite graph; as well as antichains, maximum antichains, c-optimal antichains, and c-optimal ideals of a poset. Specifically, the delay and space required by these algorithms are polynomial in the size of the matroid ground set, graph, or poset, respectively. Furthermore, all of these listings correspond to Hamilton paths on the corresponding combinatorial polytopes, namely the base polytope, matching polytope, vertex cover polytope, stable set polytope, chain polytope and order polytope, respectively. As another corollary from our framework, we obtain an O(t_LP log n) delay algorithm for the vertex enumeration problem on 0/1-polytopes {x is is from R^n l A x &lt;= b}, where A is from R^{m x n} and b is from R^m, and t_LP is the time needed to solve the linear program min {w . x ; A x &lt;= b}. This improves upon the 25-year old O(t_LP n) delay algorithm due to Bussieck and Lübbecke.

Název v anglickém jazyce

Traversing combinatorial 0/1-polytopes via optimization

Popis výsledku anglicky

In this paper, we present a new framework that exploits combinatorial optimization for efficiently generating a large variety of combinatorial objects based on graphs, matroids, posets and polytopes. Our method relies on a simple and versatile algorithm for computing a Hamilton path on the skeleton of any 0/1-polytope conv(X), where X is a subset of  {0,1}^n. The algorithm uses as a black box any algorithm that solves a variant of the classical linear optimization problem min {w . x ; x is from X}, and the resulting delay, i.e., the running time per visited vertex on the Hamilton path, is only by a factor of log n larger than the running time of the optimization algorithm. When X encodes a particular class of combinatorial objects, then traversing the skeleton of the polytope conv(X) along a Hamilton path corresponds to listing the combinatorial objects by local change operations, i.e., we obtain Gray code listings. As concrete results of our general framework, we obtain efficient algorithms for generating all (c-optimal) bases and independent sets in a matroid; (c-optimal) spanning trees, forests, matchings, maximum matchings, and c-optimal matchings in a general graph; vertex covers, minimum vertex covers, c-optimal vertex covers, stable sets, maximum stable sets and c-optimal stable sets in a bipartite graph; as well as antichains, maximum antichains, c-optimal antichains, and c-optimal ideals of a poset. Specifically, the delay and space required by these algorithms are polynomial in the size of the matroid ground set, graph, or poset, respectively. Furthermore, all of these listings correspond to Hamilton paths on the corresponding combinatorial polytopes, namely the base polytope, matching polytope, vertex cover polytope, stable set polytope, chain polytope and order polytope, respectively. As another corollary from our framework, we obtain an O(t_LP log n) delay algorithm for the vertex enumeration problem on 0/1-polytopes {x is is from R^n l A x &lt;= b}, where A is from R^{m x n} and b is from R^m, and t_LP is the time needed to solve the linear program min {w . x ; A x &lt;= b}. This improves upon the 25-year old O(t_LP n) delay algorithm due to Bussieck and Lübbecke.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA22-15272S" target="_blank" >GA22-15272S: Principy kombinatorického generování</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2023

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings - IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS

ISBN

979-8-3503-1894-4

ISSN

2575-8454

e-ISSN

—

Počet stran výsledku

10

Strana od-do

1282-1291

Název nakladatele

IEEE Computer Society

Místo vydání

Santa Cruz

Místo konání akce

Santa Cruz, USA

Datum konání akce

6. 11. 2023

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—