scientific article; zbMATH DE number 7559153
From MaRDI portal
Publication:5090494
DOI10.4230/LIPIcs.STACS.2019.44zbMath1499.68132arXiv1811.01296MaRDI QIDQ5090494
Michał Pilipczuk, Marcin Wrochna, Dušan Knop
Publication date: 18 July 2022
Full work available at URL: https://arxiv.org/abs/1811.01296
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Integer programming (90C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (6)
About the Complexity of Two-Stage Stochastic IPs ⋮ On the Decision Tree Complexity of Threshold Functions ⋮ On the optimality of pseudo-polynomial algorithms for integer programming ⋮ The double exponential runtime is tight for 2-stage stochastic ILPs ⋮ On some FPT problems without polynomial Turing compressions ⋮ On the decision tree complexity of threshold functions
Cites Work
- Sparsity. Graphs, structures, and algorithms
- A simplified NP-complete satisfiability problem
- An application of simultaneous diophantine approximation in combinatorial optimization
- Which problems have strongly exponential complexity?
- \(n\)-fold integer programming in cubic time
- Scheduling meets \(n\)-fold integer programming
- Finiteness theorems in stochastic integer programming
- Integer Programming with a Fixed Number of Variables
- Minkowski's Convex Body Theorem and Integer Programming
- On the complexity of integer programming
- Faster Algorithms for Integer Programs with Block Structure
- A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
- On the Optimality of Pseudo-polynomial Algorithms for Integer Programming
- On Integer Programming and Convolution.
- Tight Lower Bounds for the Complexity of Multicoloring
- SETH-Based Lower Bounds for Subset Sum and Bicriteria Path
- On a Combinatorial Problem in Number Theory
- Parameterized Algorithms
- Determination of a Subset from Certain Combinatorial Properties
- Optimal reconstruction of graphs under the additive model
- On the complexity of \(k\)-SAT
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication:
