Constant-factor approximation algorithms for parity-constrained facility location and \(k\)-center

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

zbMATH Keywords

approximation algorithms\(k\)-centerfacility location problemsclustering problemsparity constraints

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

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

This page was built for publication: Constant-factor approximation algorithms for parity-constrained facility location and \(k\)-center