Constant-factor approximation algorithms for parity-constrained facility location and \(k\)-center
From MaRDI portal
Publication:6107886
DOI10.1007/s00453-022-01060-5arXiv1907.03129MaRDI QIDQ6107886
Yongho Shin, Hyung-Chan An, Unnamed Author
Publication date: 28 June 2023
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1907.03129
approximation algorithms; \(k\)-center; facility location problems; clustering problems; parity constraints
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Corrigendum to our paper The ellipsoid method and its consequences in combinatorial optimization
- Centrality of trees for capacitated \(k\)-center
- The ellipsoid method and its consequences in combinatorial optimization
- Weakly bipartite graphs and the max-cut problem
- Packing odd paths
- Path parity and perfection
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Approximating minimum-cost connected \(T\)-joins
- Approximation Algorithms for Facility Location with Capacitated and Length-Bounded Tree Connections
- A 5-Approximation for Capacitated Facility Location
- Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
- LP-Based Algorithms for Capacitated Facility Location
- A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem
- Approximating Airports and Railways
- Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Facility Location in Dynamic Geometric Data Streams
- A new greedy approach for facility location problems
- A Best Possible Heuristic for the k-Center Problem
- Odd Minimum Cut-Sets and b-Matchings
- The Capacitated K-Center Problem
- Analysis of a Local Search Heuristic for Facility Location Problems
- Matching, Euler tours and the Chinese postman
- Eight-Fifth Approximation for the Path TSP
- Approximation algorithms for a facility location problem with service capacities
- Facility Location in Evolving Metrics
- On Facility Location with General Lower Bounds
- Approximating k-center in planar graphs
- Local-Search based Approximation Algorithms for Mobile Facility Location Problems: (Extended Abstract)
- An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem
