To close is easier than to open: dual parameterization to k-median

DOI10.1007/978-3-030-80879-2_8MaRDI QIDQ2117693zbMATH OpenOpenAlexFDO

Authors Jaroslaw Byrka, Szymon Dudycz, Pasin Manurangsi, Jan Marcinkowski, Michał Włodarczyk

Publication date 22 March 2022

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

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Approximation algorithms (68W25)

Cites work

• scientific article; zbMATH DE number 1775395 (Why is no real title available?)
• scientific article; zbMATH DE number 7561535 (Why is no real title available?)
• A birthday repetition theorem and complexity of approximating dense CSPs
• A constant FPT approximation algorithm for hard-capacitated \(k\)-means
• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)
• A tight bound on approximating arbitrary metrics by tree metrics
• A tight lower bound for planar Steiner orientation
• An FPT algorithm beating 2-approximation for \(k\)-cut
• An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization
• An approximation algorithm for uniform capacitated \(k\)-median problem with \(1+\epsilon\) capacity violation
• Analysis of a Local Search Heuristic for Facility Location Problems
• Approximating capacitated \(k\)-median with \((1 + \epsilon)k\) open facilities
• Color-coding
• Constant approximation for capacitated \(k\)-median with \((1+\epsilon)\)-capacity violation
• Constant-Factor FPT Approximation for Capacitated k-Median
• Greedy Strikes Back: Improved Facility Location Algorithms
• Local Search Heuristics for k-Median and Facility Location Problems
• Lossy kernelization
• On the fixed-parameter tractability of capacitated clustering
• On uniform capacitated \(k\)-median beyond the natural LP relaxation
• Parameterized Complexity and Approximability of Directed Odd Cycle Transversal
• Parameterized algorithms
• Parameterized approximation algorithms for bidirected Steiner network problems
• Parameterized intractability of even set and shortest vector problem from Gap-ETH
• SOFSEM 2006: Theory and Practice of Computer Science
• Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)

This page was built for publication: To close is easier than to open: dual parameterization to \(k\)-median

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2117693)