A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time
From MaRDI portal
Publication:5874522
DOI10.4230/LIPIcs.ESA.2020.52OpenAlexW3082510923MaRDI QIDQ5874522
Chaitanya Swamy, Zachary Friggstad
Publication date: 7 February 2023
Full work available at URL: http://arxiv.org/pdf/1912.06198.pdf
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- The delivery man problem on a tree network
- The school bus routing problem: a review
- Konstruktion aller n-fach kantenzusammenhaengenden Digraphen
- Approximating minimum-cost graph problems with spanning tree edges
- Compact, provably-good LPs for orienteering and regret-bounded vehicle routing
- The Vehicle Routing Problem
- The minimum latency problem
- Asymmetric Traveling Salesman Path and Directed Latency Problems
- Facility Location with Client Latencies: Linear Programming Based Techniques for Minimum Latency Problems
- Improving Christofides' Algorithm for the s-t Path TSP
- An Improved Integrality Gap for Asymmetric TSP Paths
- The Directed Minimum Latency Problem
- The complexity of the travelling repairman problem
- The Delivery Man Problem and Cumulative Matroids
- Preserving and Increasing Local Edge-Connectivity in Mixed Graphs
- An improved approximation algorithm for ATSP
- A constant-factor approximation algorithm for the asymmetric traveling salesman problem
- Approximation algorithms for regret-bounded vehicle routing and applications to distance-constrained vehicle routing
- Linear Programming-based Approximation Algorithms for Multi-Vehicle Minimum Latency Problems (Extended Abstract)
- Approximation Algorithms for Orienteering and Discounted-Reward TSP
- On the Integrality Ratio for the Asymmetric Traveling Salesman Problem
- List Scheduling in Order of α-Points on a Single Machine
- The asymmetric traveling salesman path LP has constant integrality ratio
This page was built for publication: A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time
