To close is easier than to open: dual parameterization to \(k\)-median
type: Item
instance of: scholarly article
title: To close is easier than to open: dual parameterization to \(k\)-median
DOI: 10.1007/978-3-030-80879-2_8
author: Jaroslaw Byrka
author: Szymon Dudycz
author: Pasin Manurangsi
author: Jan Marcinkowski
author: Michał Włodarczyk
publication date: 2022-03-22T00:00:00Z
full work available at URL: https://arxiv.org/abs/2011.08083
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68W27
zbMATH DE Number: 7495122
MaRDI profile type: Publication
OpenAlex ID: W3184443380
cites work: Constant-Factor FPT Approximation for Capacitated k-Median
cites work: Color-coding
cites work: Local Search Heuristics for k-Median and Facility Location Problems
cites work: Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH
cites work: An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization
cites work: An Approximation Algorithm for Uniform Capacitated k-Median Problem with $$1+\epsilon $$ Capacity Violation
cites work: Q4542528
cites work: A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)
cites work: Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
cites work: A tight lower bound for planar Steiner orientation
cites work: Q5091192
cites work: Q5091191
cites work: Parameterized Algorithms
cites work: SOFSEM 2006: Theory and Practice of Computer Science
cites work: Q4598213
cites work: A tight bound on approximating arbitrary metrics by tree metrics
cites work: Greedy Strikes Back: Improved Facility Location Algorithms
cites work: Q4608074
cites work: Analysis of a Local Search Heuristic for Facility Location Problems
cites work: On Uniform Capacitated k-Median Beyond the Natural LP Relaxation
cites work: Approximating capacitated k-median with (1 + ∊)k open facilities
cites work: Lossy kernelization
cites work: Parameterized Complexity and Approximability of Directed Odd Cycle Transversal
cites work: Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)
cites work: Q5111409
cites work: A constant FPT approximation algorithm for hard-capacitated \(k\)-means
description: scientific article; zbMATH DE number 7495122