Polynomial kernels for weighted problems
From MaRDI portal
Publication:340549
DOI10.1016/j.jcss.2016.06.004zbMath1353.68122arXiv1507.03439OpenAlexW2230017674MaRDI QIDQ340549
Stefan Kratsch, Heiko Röglin, Matthias Mnich, Michael Etscheid
Publication date: 14 November 2016
Published in: Journal of Computer and System Sciences, Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1507.03439
knapsacksubset sumFPTinteger linear programming with bounded variableskernelization for weighted parameterized problems
Related Items (17)
Parameterized Resiliency Problems via Integer Linear Programming ⋮ Problems on finite automata and the exponential time hypothesis ⋮ The complexity of speedrunning video games ⋮ Change-making problems revisited: a parameterized point of view ⋮ On the parameterized complexity of the connected flow and many visits TSP problem ⋮ Knapsack problems: a parameterized point of view ⋮ Parameterized algorithms and data reduction for the short secluded s‐t‐path problem ⋮ A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics ⋮ On approximate data reduction for the Rural Postman Problem: Theory and experiments ⋮ Parameterized complexity for iterated type partitions and modular-width ⋮ Polynomial-time data reduction for weighted problems beyond additive goal functions ⋮ Unnamed Item ⋮ Pattern matching and consensus problems on weighted sequences and profiles ⋮ Parameterized complexity of machine scheduling: 15 open problems ⋮ Subexponential parameterized algorithms and kernelization on almost chordal graphs ⋮ Kernelization of Graph Hamiltonicity: Proper $H$-Graphs ⋮ Parameterized resiliency problems
Cites Work
- Unnamed Item
- Kernel bounds for disjoint cycles and disjoint paths
- Parameterizing by the number of numbers
- On problems without polynomial kernels
- An application of simultaneous diophantine approximation in combinatorial optimization
- Which problems have strongly exponential complexity?
- Bin packing with fixed number of bins revisited
- On simultaneous approximation in quadratic integer programming
- Crown reductions for the minimum weighted vertex cover problem
- On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility
- Reducing a Target Interval to a Few Exact Queries
- Integer Programming with a Fixed Number of Variables
- On the Compressibility of $\mathcal{NP}$ Instances and Cryptographic Applications
- Intersection Theorems for Systems of Sets
- Minkowski's Convex Body Theorem and Integer Programming
- Kernelization Lower Bounds by Cross-Composition
- Fixed-Parameter Algorithms for Minimum Cost Edge-Connectivity Augmentation
This page was built for publication: Polynomial kernels for weighted problems
