Polynomial kernels for weighted problems

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

zbMATH Keywords

knapsacksubset sumFPTinteger linear programming with bounded variableskernelization for weighted parameterized problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

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