Idioma:

On the optimality of pseudo-polynomial algorithms for integer programming

Fomin, Fedor V. ; Panolan, Fahad ; Ramanujan, M. S. ; Saurabh, Saket

Mathematical programming, 2023-03, Vol.198 (1), p.561-593 [Revista revisada por pares]

Berlin/Heidelberg: Springer Berlin Heidelberg

Texto completo disponible

Citas Citado por

Acciones

Título:
On the optimality of pseudo-polynomial algorithms for integer programming
Autor: Fomin, Fedor V. ; Panolan, Fahad ; Ramanujan, M. S. ; Saurabh, Saket
Materias: Algorithms ; Calculus of Variations and Optimal Control; Optimization ; Combinatorics ; Complexity ; Full Length Paper ; Integer programming ; Lower bounds ; Mathematical analysis ; Mathematical and Computational Physics ; Mathematical Methods in Physics ; Mathematics ; Mathematics and Statistics ; Mathematics of Computing ; Matrices (mathematics) ; Numerical Analysis ; Optimization ; Parameters ; Polynomials ; Run time (computers) ; Theoretical ; Upper bounds
Es parte de: Mathematical programming, 2023-03, Vol.198 (1), p.561-593
Descripción: In the classic Integer Programming Feasibility (IPF) problem, the objective is to decide whether, for a given m × n matrix A and an m -vector b = ( b 1 , ⋯ , b m ) , there is a non-negative integer n -vector x such that A x = b . Solving (IPF) is an important step in numerous algorithms and it is important to obtain an understanding of the precise complexity of this problem as a function of natural parameters of the input. The classic pseudo-polynomial time algorithm of Papadimitriou [J. ACM 1981] for instances of (IPF) with a constant number of constraints was only recently improved upon by Eisenbrand and Weismantel [SODA 2018] and Jansen and Rohwedder [ITCS 2019]. Jansen and Rohwedder designed an algorithm for (IPF) with running time O ( m Δ ) m log ( Δ ) log ( Δ + ‖ b ‖ ∞ ) + O ( m n ) . Here, Δ is an upper bound on the absolute values of the entries of A . We continue this line of work and show that under the Exponential Time Hypothesis (ETH), the algorithm of Jansen and Rohwedder is nearly optimal, by proving a lower bound of n o ( m log m ) · ‖ b ‖ ∞ o ( m ) . We also prove that assuming ETH, (IPF) cannot be solved in time f ( m ) · ( n · ‖ b ‖ ∞ ) o ( m log m ) for any computable function f . This motivates us to pick up the line of research initiated by Cunningham and Geelen [IPCO 2007] who studied the complexity of solving (IPF) with non-negative matrices in which the number of constraints may be unbounded, but the branch-width of the column-matroid corresponding to the constraint matrix is a constant. We prove a lower bound on the complexity of solving (IPF) for such instances and obtain optimal results with respect to a closely related parameter, path-width. Specifically, we prove matching upper and lower bounds for (IPF) when the path-width of the corresponding column-matroid is a constant .
Editor: Berlin/Heidelberg: Springer Berlin Heidelberg
Idioma: Inglés

Volver a la lista de resultados

Anterior Resultado 4 Siguiente Ir a la siguiente página

Realización: Logos de Redes Sociales:

On the optimality of pseudo-polynomial algorithms for integer programming

Fomin, Fedor V. ; Panolan, Fahad ; Ramanujan, M. S. ; Saurabh, Saket

Berlin/Heidelberg: Springer Berlin Heidelberg

Buscando en bases de datos remotas, por favor espere