Polynomial kernels for weighted problems
From MaRDI portal
Publication:340549
DOI10.1007/978-3-662-48054-0_24zbMATH Open1353.68122arXiv1507.03439OpenAlexW2230017674MaRDI QIDQ340549FDOQ340549
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)
Abstract: Kernelization is a formalization of efficient preprocessing for NP-hard problems using the framework of parameterized complexity. Among open problems in kernelization it has been asked many times whether there are deterministic polynomial kernelizations for Subset Sum and Knapsack when parameterized by the number of items. We answer both questions affirmatively by using an algorithm for compressing numbers due to Frank and Tardos (Combinatorica 1987). This result had been first used by Marx and V'egh (ICALP 2013) in the context of kernelization. We further illustrate its applicability by giving polynomial kernels also for weighted versions of several well-studied parameterized problems. Furthermore, when parameterized by the different item sizes we obtain a polynomial kernelization for Subset Sum and an exponential kernelization for Knapsack. Finally, we also obtain kernelization results for polynomial integer programs.
Full work available at URL: https://arxiv.org/abs/1507.03439
Recommendations
subset sumknapsackFPTinteger linear programming with bounded variableskernelization for weighted parameterized problems
Cites Work
- On the Compressibility of $\mathcal{NP}$ Instances and Cryptographic Applications
- On problems without polynomial kernels
- Which problems have strongly exponential complexity?
- Integer Programming with a Fixed Number of Variables
- Minkowski's Convex Body Theorem and Integer Programming
- On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility
- Intersection Theorems for Systems of Sets
- Kernelization Lower Bounds by Cross-Composition
- An application of simultaneous diophantine approximation in combinatorial optimization
- Kernel bounds for disjoint cycles and disjoint paths
- Bin packing with fixed number of bins revisited
- On simultaneous approximation in quadratic integer programming
- Crown reductions for the minimum weighted vertex cover problem
- Reducing a Target Interval to a Few Exact Queries
- Title not available (Why is that?)
- Fixed-Parameter Algorithms for Minimum Cost Edge-Connectivity Augmentation
- Parameterizing by the number of numbers
Cited In (19)
- Title not available (Why is that?)
- Parameterized resiliency problems
- Pattern matching and consensus problems on weighted sequences and profiles
- Kernelization of Graph Hamiltonicity: Proper $H$-Graphs
- Parameterized complexity of machine scheduling: 15 open problems
- The complexity of speedrunning video games
- 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
- Subexponential parameterized algorithms and kernelization on almost chordal graphs
- Parameterized and approximation algorithms for the maximum bimodal subgraph problem
- Problems on finite automata and the exponential time hypothesis
- Knapsack problems: a parameterized point of view
- Parameterized Resiliency Problems via Integer Linear Programming
- On the parameterized complexity of the connected flow and many visits TSP problem
- Change-making problems revisited: a parameterized point of view
- Serial batching to minimize the weighted number of tardy jobs
- Polynomial-time data reduction for weighted problems beyond additive goal functions
- Parameterized algorithms and data reduction for the short secluded s‐t‐path problem
- Parameterized complexity for iterated type partitions and modular-width
This page was built for publication: Polynomial kernels for weighted problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q340549)
