Facility Location with Client Latencies: Linear Programming Based Techniques for Minimum Latency Problems

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

zbMATH Keywords

approximation algorithmslinear programming relaxationsfacilty locationlatency problems

Mathematics Subject Classification ID

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

• VRP

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