Combinatorial \(n\)-fold integer programming and applications
From MaRDI portal
Publication:2205969
DOI10.1007/s10107-019-01402-2zbMath1451.90100arXiv1705.08657OpenAlexW2963004262WikidataQ126775401 ScholiaQ126775401MaRDI QIDQ2205969
Matthias Mnich, Martin Koutecký, Dušan Knop
Publication date: 21 October 2020
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1705.08657
Related Items (11)
Parameterized complexity of configuration integer programs ⋮ 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? ⋮ A multivariate complexity analysis of the material consumption scheduling problem ⋮ Unnamed Item ⋮ Approximation and hardness of shift-Bribery ⋮ The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints ⋮ A parameterized perspective on protecting elections ⋮ Empowering the configuration-IP: new PTAS results for scheduling with setup times ⋮ Moderate exponential-time algorithms for scheduling problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On polynomial kernels for sparse integer linear programs
- Parameterized complexity analysis for the closest string with wildcards problem
- Parameterized complexity of coloring problems: treewidth versus vertex cover
- On covering problems of codes
- Parameterizing by the number of numbers
- Efficient algorithms for consensus string problems minimizing both distance sum and radius
- Scheduling and fixed-parameter tractability
- Nonlinear discrete optimization. An algorithmic theory
- Geometric algorithms and combinatorial optimization.
- Fixed-parameter algorithms for CLOSEST STRING and related problems
- Distinguishing string selection problems.
- Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity
- The complexity landscape of decompositional parameters for ILP
- Multivariate complexity analysis of Swap Bribery
- Algorithmic meta-theorems for restrictions of treewidth
- Parameterized complexity of machine scheduling: 15 open problems
- \(n\)-fold integer programming in cubic time
- Graver basis and proximity techniques for block-structured separable convex integer minimization problems
- Scheduling meets \(n\)-fold integer programming
- Huge multiway table problems
- Parameterized complexity of distance labeling and uniform channel assignment problems
- Carathéodory bounds for integer cones
- A Polynomial-Time Descent Method for Separable Convex Optimization Problems with Linear Constraints
- Parameterized Algorithms for Modular-Width
- Integer Programming with a Fixed Number of Variables
- On the closest string and substring problems
- Closest Substring Problems with Small Distances
- Elections with Few Candidates: Prices, Weights, and Covering Problems
- A Structural Approach to Kernels for ILPs: Treewidth and Total Unimodularity
- Huge Unimodular $n$-Fold Programs
- Algorithms for Temperature-Aware Task Scheduling in Microprocessor Systems
- More Efficient Algorithms for Closest String and Substring Problems
- Graph Layout Problems Parameterized by Vertex Cover
- Swap Bribery
- How Hard Is Bribery in Elections?
- Minkowski's Convex Body Theorem and Integer Programming
- On the complexity of integer programming
- Condorcet Social Choice Functions
- About the Structure of the Integer Cone and its Application to Bin Packing
- Enumerating Neighbour and Closest Strings
- Faster Algorithms for Integer Programs with Block Structure
- A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
- On Integer Programming and Convolution.
- A linear-time algorithm for the 1-mismatch problem
- On the Efficiency of the Hamming C-Centerstring Problems
- Mathematical Foundations of Computer Science 2004
- Polynomiality for Bin Packing with a Constant Number of Item Types
- A Multivariate Complexity Analysis of Lobbying in Multiple Referenda
- Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
- Parameterized Algorithms
- Convex separable optimization is not much harder than linear optimization
This page was built for publication: Combinatorial \(n\)-fold integer programming and applications
