Reverse greedy is bad for \(k\)-center

DOI10.1016/j.ipl.2020.105941zbMath1432.68574arXiv1810.01834OpenAlexW3011294827MaRDI QIDQ2308462

Gregory Kehne, D. Ellis Hershkowitz

Publication date: 3 April 2020

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

combinatorial optimizationfacility locationapproximation algorithmsreverse greedy

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Discrete location and assignment (90B80) Approximation algorithms (68W25)

Cites Work

• Center-based clustering under perturbation stability
• Easy and hard bottleneck location problems
• The ordered \(k\)-median problem: surrogate models and approximation algorithms
• A constant-factor approximation algorithm for the k -median problem (extended abstract)
• A Best Possible Heuristic for the k-Center Problem
• Approximation algorithms for minimum norm and ordered optimization problems
• Constant-factor approximation for ordered k-median
• Computing and Combinatorics
• Clustering under Perturbation Resilience
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Reverse greedy is bad for \(k\)-center