A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time
From MaRDI portal
Publication:5874522
DOI10.4230/LIPICS.ESA.2020.52OpenAlexW3082510923MaRDI QIDQ5874522FDOQ5874522
Authors: Zachary Friggstad, Chaitanya Swamy 
Publication date: 7 February 2023
Full work available at URL: http://arxiv.org/pdf/1912.06198.pdf
Cites Work
- The vehicle routing problem
- Title not available (Why is that?)
- The minimum latency problem
- The complexity of the travelling repairman problem
- The delivery man problem on a tree network
- The Delivery Man Problem and Cumulative Matroids
- On the Integrality Ratio for the Asymmetric Traveling Salesman Problem
- Facility location with client latencies: linear programming based techniques for minimum latency problems
- Approximation algorithms for regret-bounded vehicle routing and applications to distance-constrained vehicle routing
- The school bus routing problem: a review
- Approximation Algorithms for Orienteering and Discounted-Reward TSP
- List Scheduling in Order of α-Points on a Single Machine
- Konstruktion aller n-fach kantenzusammenhaengenden Digraphen
- Preserving and Increasing Local Edge-Connectivity in Mixed Graphs
- Linear Programming-based Approximation Algorithms for Multi-Vehicle Minimum Latency Problems (Extended Abstract)
- The Directed Minimum Latency Problem
- An improved approximation algorithm for ATSP
- Approximating minimum-cost graph problems with spanning tree edges
- Improving Christofides' Algorithm for the s-t Path TSP
- Asymmetric traveling salesman path and directed latency problems
- A constant-factor approximation algorithm for the asymmetric traveling salesman problem
- Compact, provably-good LPs for orienteering and regret-bounded vehicle routing
- An improved integrality gap for asymmetric TSP paths
- Title not available (Why is that?)
- The asymmetric traveling salesman path LP has constant integrality ratio
Uses Software
This page was built for publication: A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5874522)
