scientific article; zbMATH DE number 7651172

DOI10.4230/LIPICS.ESA.2020.33MaRDI QIDQ5874501zbMATH OpenFDO

Authors Lin Chen, Martin Koutecký, Weidong (Larry) Shi, Lei Xu

Publication date 7 February 2023

Full work available at URL https://arxiv.org/abs/1805.03741

zbMATH Keywords

fixed parameter tractablegraver basisinteger programming

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• On Block-Structured Integer Programming and Its Applications
• scientific article; zbMATH DE number 647691
• On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond
• On the augmented Lagrangian dual for integer programming
• Faster Algorithms for Integer Programs with Block Structure
• A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
• An augmented Lagrangian decomposition method for block diagonal linear programming problems
• The blockwise coordinate descent method for integer programs
• Mixed decomposition in block integer linear programming problems
• Pseudo basic steps: bound improvement guarantees from Lagrangian decomposition in convex disjunctive programming

Cites work

• \(N\)-fold integer programming
• \(n\)-fold integer programming in cubic time
• A finiteness theorem for Markov bases of hierarchical models
• A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
• A polynomial oracle-time algorithm for convex integer minimization
• A strongly polynomial algorithm for bimodular integer linear programming
• About the Complexity of Two-Stage Stochastic IPs
• Combinatorial \(n\)-fold integer programming and applications
• Covering a tree with rooted subtrees -- parameterized and approximation algorithms
• Empowering the configuration-IP -- new PTAS results for scheduling with setups times
• Faster Algorithms for Integer Programs with Block Structure
• Finiteness theorems in stochastic integer programming
• Graver basis and proximity techniques for block-structured separable convex integer minimization problems
• scientific article; zbMATH DE number 1688600 (Why is no real title available?)
• scientific article; zbMATH DE number 6850361 (Why is no real title available?)
• Lower bounds on the graver complexity of M-fold matrices
• Nonlinear discrete optimization. An algorithmic theory
• On integer programming and convolution
• On the complexity of integer programming
• On the foundations of linear and integer linear programming I
• Optimization with binet matrices
• Reducibility among combinatorial problems
• Scheduling meets n-fold integer programming
• The complexity landscape of decompositional parameters for ILP
• Value of the Steinitz constant
• Voting and bribing in single-exponential time

Cited in

(9)

• About the complexity of two-stage stochastic IPs
• Block-structured integer programming: can we parameterize without the largest coefficient?
• On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond
• The double exponential runtime is tight for 2-stage stochastic ILPs
• The double exponential runtime is tight for 2-stage stochastic ILPs
• A colorful Steinitz lemma with application to block-structured integer programs
• FPT algorithms for a special block-structured integer program with applications in scheduling
• Parameterized algorithms for block-structured integer programs with large entries
• Solving 4-block integer linear programs faster using affine decompositions of the right-hand sides

This page was built for publication:

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