Faster algorithms for sparse ILP and hypergraph multi-packing/multi-cover problems

Dmitry Gribanov (), Ivan Shumilov (), Dmitry Malyshev () and Nikolai Zolotykh ()
Additional contact information
Dmitry Gribanov: HSE University
Ivan Shumilov: Lobachevsky State University of Nizhny Novgorod
Dmitry Malyshev: HSE University
Nikolai Zolotykh: Lobachevsky State University of Nizhni Novgorod

Journal of Global Optimization, 2024, vol. 89, issue 4, No 8, 1033-1067

Abstract: Abstract In our paper, we consider the following general problems: check feasibility, count the number of feasible solutions, find an optimal solution, and count the number of optimal solutions in $${{\,\mathrm{\mathcal {P}}\,}}\cap {{\,\mathrm{\mathbb {Z}}\,}}^n$$ P ∩ Z n , assuming that $${{\,\mathrm{\mathcal {P}}\,}}$$ P is a polyhedron, defined by systems $$A x \le b$$ A x ≤ b or $$Ax = b,\, x \ge 0$$ A x = b , x ≥ 0 with a sparse matrix A. We develop algorithms for these problems that outperform state-of-the-art ILP and counting algorithms on sparse instances with bounded elements in terms of the computational complexity. Assuming that the matrix A has bounded elements, our complexity bounds have the form $$s^{O(n)}$$ s O ( n ) , where s is the minimum between numbers of non-zeroes in columns and rows of A, respectively. For $$s = o\bigl (\log n \bigr )$$ s = o ( log n ) , this bound outperforms the state-of-the-art ILP feasibility complexity bound $$(\log n)^{O(n)}$$ ( log n ) O ( n ) , due to Reis & Rothvoss (in: 2023 IEEE 64th Annual symposium on foundations of computer science (FOCS), IEEE, pp. 974–988). For $$s = \phi ^{o(\log n)}$$ s = ϕ o ( log n ) , where $$\phi $$ ϕ denotes the input bit-encoding length, it outperforms the state-of-the-art ILP counting complexity bound $$\phi ^{O(n \log n)}$$ ϕ O ( n log n ) , due to Barvinok et al. (in: Proceedings of 1993 IEEE 34th annual foundations of computer science, pp. 566–572, https://doi.org/10.1109/SFCS.1993.366830 , 1993), Dyer, Kannan (Math Oper Res 22(3):545–549, https://doi.org/10.1287/moor.22.3.545 , 1997), Barvinok, Pommersheim (Algebr Combin 38:91–147, 1999), Barvinok (in: European Mathematical Society, ETH-Zentrum, Zurich, 2008). We use known and new methods to develop new exponential algorithms for Edge/Vertex Multi-Packing/Multi-Cover Problems on graphs and hypergraphs. This framework consists of many different problems, such as the Stable Multi-set, Vertex Multi-cover, Dominating Multi-set, Set Multi-cover, Multi-set Multi-cover, and Hypergraph Multi-matching problems, which are natural generalizations of the standard Stable Set, Vertex Cover, Dominating Set, Set Cover, and Maximum Matching problems.

Keywords: Integer linear programming; Counting problem; Parameterized complexity; Multipacking; Multicover; Stable set; Vertex cover; Dominating set; Multiset multicover; Hypergraph matching; Sparse matrix (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-024-01379-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:89:y:2024:i:4:d:10.1007_s10898-024-01379-z

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-024-01379-z

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().