Integer programming in parameterized complexity: five miniatures
From MaRDI portal
Publication:2673236
DOI10.1016/j.disopt.2020.100596OpenAlexW3044145206MaRDI QIDQ2673236
Martin Koutecký, Dušan Knop, Tomáš Gavenčiak
Publication date: 9 June 2022
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disopt.2020.100596
Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Parameterized complexity for iterated type partitions and modular-width ⋮ Spanning trees with few branch vertices in graphs of bounded neighborhood diversity ⋮ Maximizing Social Welfare in Score-Based Social Distance Games ⋮ On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Complexity of conflict-free colorings of graphs
- Scheduling and fixed-parameter tractability
- FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension
- Nonlinear discrete optimization. An algorithmic theory
- An application of simultaneous diophantine approximation in combinatorial optimization
- On integer points in polyhedra
- Algorithmic meta-theorems for restrictions of treewidth
- Integer convex minimization by mixed integer linear optimization
- Parameterized complexity of vertex colouring
- The quadratic Graver cone, quadratic integer minimization, and extensions
- A new Lenstra-type algorithm for quasiconvex polynomial integer minimization with complexity \(2^{O(n\log n)}\)
- \(n\)-fold integer programming in cubic time
- Integer optimization on convex semialgebraic sets
- Parameterized complexity of fair deletion problems
- The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints
- Integer programming and incidence treedepth
- Scheduling meets \(n\)-fold integer programming
- Complexity of integer quasiconvex polynomial optimization
- Finiteness theorems in stochastic integer programming
- Parameterized Algorithms for Modular-Width
- What’s Next? Future Directions in Parameterized Complexity
- On the (Parameterized) Complexity of Recognizing Well-Covered $$(r,\ell )$$ -graphs
- Integer Programming with a Fixed Number of Variables
- Parametric Integer Programming in Fixed Dimension
- Elections with Few Candidates: Prices, Weights, and Covering Problems
- A Structural Approach to Kernels for ILPs: Treewidth and Total Unimodularity
- Capacitated Domination and Covering: A Parameterized Perspective
- Nonlinear Integer Programming
- An OPT + 1 Algorithm for the Cutting Stock Problem with Constant Number of Object Lengths
- A Game Theoretic Approach for Efficient Graph Coloring
- Graph Layout Problems Parameterized by Vertex Cover
- Minkowski's Convex Body Theorem and Integer Programming
- On the complexity of integer programming
- Approximation results for the optimum cost chromatic partition problem
- An FPTAS for Minimizing Indefinite Quadratic Forms over Integers in Polyhedra
- Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
- A strongly polynomial algorithm for bimodular integer linear programming
- Faster Algorithms for Integer Programs with Block Structure
- A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
- Integer Programming in Parameterized Complexity: Three Miniatures.
- About the Complexity of Two-Stage Stochastic IPs
- Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints
- Near-optimal deterministic algorithms for volume computation via M-ellipsoids
- Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
- Subdeterminants and Concave Integer Quadratic Programming
- Parameterized Resiliency Problems via Integer Linear Programming
- Mathematical Foundations of Computer Science 2004
- Scheduling Two Competing Agents When One Agent Has Significantly Fewer Jobs
- Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
- Parameterized shifted combinatorial optimization
