5 papers · 1 filter
Tight Approximations for Fixed-Order Vehicle Routing with Stochastic Demands
Jingyang Zhao, Mingyu Xiao
We study the vehicle routing problem (VRP) with stochastic demands, where each client has an independent demand with a known distribution, and its realized demand is observed only…
A -Approximation for the Multiple-Depot Traveling Salesman Problem
Jingyang Zhao, Yuxi Liu, Mingyu Xiao
The metric traveling salesman problem (TSP) is a fundamental problem in combinatorial optimization that asks for a minimum-cost tour covering all clients in a metric graph. The met…
Approximating Unsplittable Capacitated Vehicle Routing: Analysis via Factor-Revealing LPs
Jingyang Zhao, Mingyu Xiao
The capacitated vehicle routing problem (CVRP) is one of the most extensively studied problems in combinatorial optimization. Given a depot and a set of customers with demands in a…
Improved Approximations for Dial-a-Ride Problems
Jingyang Zhao, Mingyu Xiao
The multi-vehicle dial-a-ride problem (mDaRP) is a fundamental vehicle routing problem with pickups and deliveries, widely applicable in ride-sharing, economics, and transportation…
Improved Approximation Algorithms for the Multiple-Depot Split Delivery Vehicle Routing Problem
Jingyang Zhao, Yonghang Su, Mingyu Xiao
The multiple-depot split delivery vehicle routing problem is a challenging optimization problem with broad applications in logistics and transportation. The goal is to serve custom…