Facility Location with Client Latencies: Linear Programming Based Techniques for Minimum Latency Problems
From MaRDI portal
DOI10.1007/978-3-642-20807-2_8zbMath1339.90193arXiv1009.2452OpenAlexW1714443387MaRDI QIDQ3009753
Deeparnab Chakrabarty, Chaitanya Swamy
Publication date: 24 June 2011
Published in: Mathematics of Operations Research, Integer Programming and Combinatoral Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1009.2452
Programming involving graphs or networks (90C35) Linear programming (90C05) Discrete location and assignment (90B80) Approximation algorithms (68W25)
Related Items (12)
A constant-factor approximation for directed latency in quasi-polynomial time ⋮ The latency location-routing problem ⋮ Combinatorial algorithms for rooted prize-collecting walks and applications to orienteering and minimum-latency problems ⋮ A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case ⋮ On coresets for fair clustering in metric and Euclidean spaces and their applications ⋮ Approximate minimum sum colorings and maximum \(k\)-colorable subgraphs of chordal graphs ⋮ A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time ⋮ On the cost of essentially fair clusterings ⋮ Facility Location with Client Latencies: Linear Programming Based Techniques for Minimum Latency Problems ⋮ Minimizing latency of capacitated \(k\)-tours ⋮ A branch-and-cut-and-price algorithm for the cumulative capacitated vehicle routing problem ⋮ Unnamed Item
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on the prize collecting traveling salesman problem
- Survivable networks, linear programming relaxations and the parsimonious property
- Analyzing the Held-Karp TSP bound: A monotonicity property with application
- Approximating min sum set cover
- Primal-dual algorithms for connected facility location problems
- The Vehicle Routing Problem
- The minimum latency problem
- Facility Location with Client Latencies: Linear Programming Based Techniques for Minimum Latency Problems
- A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem
- A Faster, Better Approximation Algorithm for the Minimum Latency Problem
- Polylogarithmic inapproximability
- Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems
- Heuristic analysis, linear programming and branch and bound
- A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
- Preserving and Increasing Local Edge-Connectivity in Mixed Graphs
- Multiple intents re-ranking
- Provisioning a virtual private network
- Linear Programming-based Approximation Algorithms for Multi-Vehicle Minimum Latency Problems (Extended Abstract)
- A tight bound on approximating arbitrary metrics by tree metrics
- An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem
This page was built for publication: Facility Location with Client Latencies: Linear Programming Based Techniques for Minimum Latency Problems
