9 papers
Improved Approximations for the Unsplittable Capacitated Vehicle Routing Problem
Jingyang Zhao, Mingyu Xiao
The capacitated vehicle routing problem (CVRP) is one of the most extensively studied problems in combinatorial optimization. In this problem, we are given a depot and a set of cus…
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 (MD-SDVRP) is a challenging problem with broad applications in logistics. The goal is to serve customers' demand using a f…
An Improved Approximation Algorithm for Maximum Weight 3-Path Packing
Jingyang Zhao, Mingyu Xiao
Given a complete graph with vertices and non-negative edge weights, where is divisible by 3, the maximum weight 3-path packing problem is to find a set of vertex-disj…
Parameterized Approximation Algorithms for TSP on Non-Metric Graphs
Jingyang Zhao, Zimo Sheng, Mingyu Xiao
The Traveling Salesman Problem (TSP) is a classic and extensively studied problem with numerous real-world applications in artificial intelligence and operations research. It is we…
An Improved Approximation Algorithm for the Capacitated Arc Routing Problem
Jingyang Zhao, Mingyu Xiao
The Capacitated Arc Routing Problem (CARP), introduced by Golden and Wong in 1981, is an important arc routing problem in Operations Research, which generalizes the famous Capacita…