A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
From MaRDI portal
Publication:5002764
DOI10.4230/LIPIcs.ICALP.2018.85zbMath1499.68153arXiv1802.05859MaRDI QIDQ5002764
Shmuel Onn, Martin Koutecký, Asaf Levin
Publication date: 28 July 2021
Full work available at URL: https://arxiv.org/abs/1802.05859
Related Items
About the Complexity of Two-Stage Stochastic IPs, The complexity of vector partition, On degree sequence optimization, Integer programming in parameterized complexity: five miniatures, Approximate separable multichoice optimization over monotone systems, High-multiplicity \(N\)-fold IP via configuration LP, A colorful Steinitz lemma with application to block-structured integer programs, Block-structured integer programming: can we parameterize without the largest coefficient?, Unnamed Item, Asymptotic behavior of Markov complexity, Combinatorial \(n\)-fold integer programming and applications, Near-Linear Time Algorithm for $n$-Fold ILPs via Color Coding, Integer Programming in Parameterized Complexity: Three Miniatures., The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints, Parameterized shifted combinatorial optimization, Unnamed Item, Unnamed Item, Unnamed Item, The clever shopper problem, Subset Selection in Sparse Matrices, Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting, On some FPT problems without polynomial Turing compressions, Empowering the configuration-IP: new PTAS results for scheduling with setup times, Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming, About the complexity of two-stage stochastic IPs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Nonlinear discrete optimization. An algorithmic theory
- Integer program with bimodular matrix
- An application of simultaneous diophantine approximation in combinatorial optimization
- The complexity landscape of decompositional parameters for ILP
- Graver basis and proximity techniques for block-structured separable convex integer minimization problems
- Finiteness theorems in stochastic integer programming
- Optimization with binet matrices
- A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
- Integer Programming with a Fixed Number of Variables
- A Structural Approach to Kernels for ILPs: Treewidth and Total Unimodularity
- On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond
- Minkowski's Convex Body Theorem and Integer Programming
- A strongly polynomial algorithm for bimodular integer linear programming
- A Faster Parameterized Algorithm for Treedepth
- Convex separable optimization is not much harder than linear optimization
