Near-Linear Time Algorithm for $n$-Fold ILPs via Color Coding
From MaRDI portal
Publication:5138974
DOI10.1137/19M1303873zbMath1462.68232arXiv1811.00950OpenAlexW3095252247MaRDI QIDQ5138974
Alexandra Lassota, Lars Rohwedder, Klaus Jansen
Publication date: 4 December 2020
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1811.00950
Related Items
Tightness of sensitivity and proximity bounds for integer linear programs ⋮ High-multiplicity \(N\)-fold IP via configuration LP ⋮ Block-structured integer programming: can we parameterize without the largest coefficient? ⋮ Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines ⋮ Algorithms for hierarchical and semi-partitioned parallel scheduling ⋮ The double exponential runtime is tight for 2-stage stochastic ILPs ⋮ The double exponential runtime is tight for 2-stage stochastic ILPs ⋮ Empowering the configuration-IP: new PTAS results for scheduling with setup times ⋮ About the complexity of two-stage stochastic IPs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- \(N\)-fold integer programming and nonlinear multi-transshipment
- \(N\)-fold integer programming
- An integer analogue of Carathéodory's theorem
- \(n\)-fold integer programming in cubic time
- Scheduling meets \(n\)-fold integer programming
- A linear-time approximation algorithm for weighted matchings in graphs
- A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
- Huge Unimodular $n$-Fold Programs
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- Color-coding
- Approximating Edit Distance in Near-Linear Time
- Faster Algorithms for Integer Programs with Block Structure
- A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
- An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
