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

DOI10.1007/978-3-030-80879-2_8OpenAlexW3184443380MaRDI QIDQ2117693FDOQ2117693

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

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

• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)
• Greedy Strikes Back: Improved Facility Location Algorithms
• Color-coding
• Parameterized Algorithms
• A tight bound on approximating arbitrary metrics by tree metrics
• Local Search Heuristics for k-Median and Facility Location Problems
• An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization
• SOFSEM 2006: Theory and Practice of Computer Science
• Analysis of a Local Search Heuristic for Facility Location Problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• An Approximation Algorithm for Uniform Capacitated k-Median Problem with $$1+\epsilon $$ Capacity Violation
• Title not available (Why is that?)
• Lossy kernelization
• Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)
• A tight lower bound for planar Steiner orientation
• Approximating capacitated k-median with (1 + ∊)k open facilities
• Title not available (Why is that?)
• On Uniform Capacitated k-Median Beyond the Natural LP Relaxation
• Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
• Title not available (Why is that?)
• Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH
• Title not available (Why is that?)
• A constant FPT approximation algorithm for hard-capacitated \(k\)-means
• Constant-Factor FPT Approximation for Capacitated k-Median
• Parameterized Complexity and Approximability of Directed Odd Cycle Transversal

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)