Lossy kernelization

DOI10.1145/3055399.3055456zbMath1370.68136arXiv1604.04111OpenAlexW2911549278MaRDI QIDQ4977974

M. S. Ramanujan, Fahad Panolan, Saket Saurabh, Daniel Lokshtanov

Publication date: 17 August 2017

Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1604.04111

zbMATH Keywords

inapproximabilityparameterized complexitykernelization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (40)

Hans Bodlaender and the Theory of Kernelization Lower Bounds ⋮ On the parameterized complexity of maximum degree contraction problem ⋮ Unnamed Item ⋮ Time-approximation trade-offs for inapproximable problems ⋮ The parameterized hardness of the \(k\)-center problem in transportation networks ⋮ On the lossy kernelization for connected treedepth deletion set ⋮ Parameterized approximation via fidelity preserving transformations ⋮ On data reduction for dynamic vector bin packing ⋮ \(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms ⋮ Parameterized algorithms and data reduction for the short secluded s‐t‐path problem ⋮ On approximate data reduction for the Rural Postman Problem: Theory and experiments ⋮ Packing arc-disjoint cycles in oriented graphs ⋮ Matroid-constrained vertex cover ⋮ Fractals for Kernelization Lower Bounds ⋮ Fixed-parameter algorithms for unsplittable flow cover ⋮ Approximate Turing Kernelization for Problems Parameterized by Treewidth ⋮ Refined notions of parameterized enumeration kernels with applications to matching cut enumeration ⋮ On the kernelization complexity of string problems ⋮ On the parameterized complexity of contraction to generalization of trees ⋮ On the approximate compressibility of connected vertex cover ⋮ Unnamed Item ⋮ Lossy kernelization of same-size clustering ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack ⋮ Parameterized complexity of geometric covering problems having conflicts ⋮ The parameterized complexity of cycle packing: indifference is not an issue ⋮ Packing Cycles Faster Than Erdos--Posa ⋮ On approximate preprocessing for domination and hitting subgraphs with connected deletion sets ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ Revisiting connected vertex cover: FPT algorithms and lossy kernels ⋮ Lossy Kernels for Hitting Subgraphs ⋮ The Parameterized Hardness of the k-Center Problem in Transportation Networks ⋮ Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds ⋮ Dynamic kernels for hitting sets and set packing ⋮ Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices ⋮ Parameterized Approximation Algorithms for Bidirected Steiner Network Problems ⋮ Lossy kernelization of same-size clustering ⋮ Partial vertex cover on graphs of bounded degeneracy ⋮ On the Parameterized Approximability of Contraction to Classes of Chordal Graphs ⋮ To close is easier than to open: dual parameterization to \(k\)-median

This page was built for publication: Lossy kernelization