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

DOI10.1007/s10898-024-01379-zMaRDI QIDQ6593834

Nikolai Yu. Zolotykh, Dmitriy V. Gribanov, Dmitriy S. Malyshev, Ivan Shumilov

Publication date: 27 August 2024

Published in: Journal of Global Optimization (Search for Journal in Brave)

stable set sparse matrix integer linear programming dominating set counting problem vertex cover parameterized complexity hypergraph matching multicover multiset multicover multipacking

Mathematics Subject Classification ID

Mixed integer programming (90C11) Combinatorial optimization (90C27)

Cites Work

On polynomial kernels for sparse integer linear programs
Approximating minimum power edge-multi-covers
Integer points in polyhedra
Dynamic programming based algorithms for set multicover and multiset multicover problems
Integer program with bimodular matrix
Discrepancy of set-systems and matrices
``Integer-making theorems
A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
Stable multi-sets
On the minors of an incidence matrix and Smith normal form
On the \(\epsilon\)-perturbation method for avoiding degeneracy
Solving the knapsack problem via \(\mathbb Z\)-transform
Approximation algorithm for the multicovering problem
On lattice point counting in \(\varDelta\)-modular polyhedra
On the maximal number of columns of a \(\varDelta \)-modular matrix
Integer conic function minimization based on the comparison oracle
A polynomial algorithm for minimizing discrete convic functions in fixed dimension
Combinatorial \(n\)-fold integer programming and applications
Improving proximity bounds using sparsity
Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting
On the complexity of quasiconvex integer minimization problem
On a hypergraph matching problem
Anti-blocking polyhedra
On cycles and the stable multi-set polytope
Effective lattice point counting in rational convex polytopes
Integer programming in parameterized complexity: five miniatures
On the optimality of pseudo-polynomial algorithms for integer programming
A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations
Solving the stable set problem in terms of the odd cycle packing number
Elections with Few Candidates: Prices, Weights, and Covering Problems
Exact Algorithms for Set Multicover and Multiset Multicover Problems
Six Standard Deviations Suffice
Sensitivity theorems in integer linear programming
Points entiers dans les polyèdres convexes
On Barvinok's Algorithm for Counting Lattice Points in Fixed Dimension
Short rational generating functions for lattice point problems
The determinant bound for discrepancy is almost tight
Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma
A reverse Minkowski theorem
A strongly polynomial algorithm for bimodular integer linear programming
On approximating the covering radius and finding dense lattice subspaces
Computing the Continuous Discretely
On largest volume simplices and sub-determinants
On Integer Programming and the Branch-Width of the Constraint Matrix
A Primal Barvinok Algorithm Based on Irrational Decompositions
Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
Linear and Integer Programming vs Linear Integration and Counting
The maximum numbers of faces of a convex polytope
Blocking and anti-blocking pairs of polyhedra
Centerpoints: A Link between Optimization and Convex Geometry
On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems
A tighter relation between hereditary discrepancy and determinant lower bound
A faster algorithm for counting the integer points number in \(\Delta \)-modular polyhedra
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item

This page was built for publication: Faster algorithms for sparse ILP and hypergraph multi-packing/multi-cover problems