The Library
Traversing combinatorial 0/1polytopes via optimization
Tools
Merino, Arturo and Mutze, Torsten (2023) Traversing combinatorial 0/1polytopes via optimization. In: IEEE Symposium on Foundations of Computer Science (FOCS), Santa Cruz, CA, USA, 0609 Nov 2023. Published in: Proceedings of FOCS 2023 (In Press)

PDF
WRAPtraversingcombinatorial01polytopesoptimizationMutze2023.pdf  Accepted Version  Requires a PDF viewer. Download (2426Kb)  Preview 
Abstract
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/1polytope $\conv(X)$, where $X\seq \{0,1\}^n$.
The algorithm uses as a black box any algorithm that solves a variant of the classical linear optimization problem~$\min\{w\cdot x\mid x\in 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 $\cO(t_{\upright{LP}} \log n)$ delay algorithm for the vertex enumeration problem on 0/1polytopes $\{x\in\mathbb{R}^n\mid Ax\leq b\}$, where $A\in \mathbb{R}^{m\times n}$ and~$b\in\mathbb{R}^m$, and $t_{\upright{LP}}$ is the time needed to solve the linear program $\min\{w\cdot x\mid Ax\leq b\}$.
This improves upon the 25year old $\cO(t_{\upright{LP}}\,n)$ delay algorithm due to Bussieck and L\"ubbecke.
Item Type:  Conference Item (Paper)  

Subjects:  Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software 

Divisions:  Faculty of Science, Engineering and Medicine > Science > Computer Science Faculty of Science, Engineering and Medicine > Science > Mathematics 

Library of Congress Subject Headings (LCSH):  Combinatorial optimization  Data processing, Mathematical optimization, Computer science  Mathematics, Computational complexity, Graph theory  Data processing, Computer algorithms, Polyhedra  Data processing, Polyhedral functions, Polyhedra  Models  
Journal or Publication Title:  Proceedings of FOCS 2023  
Publisher:  IEEE  
Official Date:  2023  
Dates: 


Status:  Peer Reviewed  
Publication Status:  In Press  
Access rights to Published version:  Restricted or Subscription Access  
Date of first compliant deposit:  11 July 2023  
Date of first compliant Open Access:  12 July 2023  
Conference Paper Type:  Paper  
Title of Event:  IEEE Symposium on Foundations of Computer Science (FOCS)  
Type of Event:  Conference  
Location of Event:  Santa Cruz, CA, USA  
Date(s) of Event:  0609 Nov 2023  
Open Access Version: 
Request changes or add full text files to a record
Repository staff actions (login required)
View Item 
Downloads
Downloads per month over past year