Near-linear time algorithm for n-fold ILPs via color coding

DOI10.4230/LIPICS.ICALP.2019.75MaRDI QIDQ5091234zbMATH OpenFDO

Authors Alexandra Lassota, Lars Rohwedder, Klaus Jansen

Publication date 21 July 2022

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2019.75

zbMATH Keywords

\(n\)-fold ILPcolor codingnear-linear time algorithm

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Recommendations

• Near-linear time algorithm for n-fold ILPs via color coding
• Combinatorial \(n\)-fold integer programming and applications
• Combinatorial \(n\)-fold integer programming and applications
• \(n\)-fold integer programming in cubic time
• Evaluating and tuning n-fold integer programming

Cites work

• \(N\)-fold integer programming
• \(N\)-fold integer programming and nonlinear multi-transshipment
• A linear-time approximation algorithm for weighted matchings in graphs
• A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
• An integer analogue of Carathéodory's theorem
• Approximating edit distance in near-linear time
• Color-coding
• Combinatorial \(n\)-fold integer programming and applications
• Empowering the configuration-IP -- new PTAS results for scheduling with setups times
• Evaluating and tuning n-fold integer programming
• Faster Algorithms for Integer Programs with Block Structure
• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• scientific article; zbMATH DE number 6850361 (Why is no real title available?)
• Huge unimodular \(n\)-fold programs
• Storing a Sparse Table with 0 (1) Worst Case Access Time

Cited in

(2)

• About the Complexity of Two-Stage Stochastic IPs
• Mathematical programming approaches for social welfare maximization

This page was built for publication: Near-linear time algorithm for \(n\)-fold ILPs via color coding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5091234)