15 papers
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…
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…
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…
Approximation Algorithms for the Cumulative Vehicle Routing Problem with Stochastic Demands
Jingyang Zhao, Mingyu Xiao
In the Cumulative Vehicle Routing Problem (Cu-VRP), we need to find a feasible itinerary for a capacitated vehicle located at the depot to satisfy customers' demand, as in the well…
An Improved Algorithm for a Bipartite Traveling Tournament in Interleague Sports Scheduling
Jingyang Zhao, Mingyu Xiao
The bipartite traveling tournament problem (BTTP) addresses inter-league sports scheduling, which aims to design a feasible bipartite tournament between two -team leagues under…
Enhanced Approximation Algorithms for the Capacitated Location Routing Problem
Jingyang Zhao, Mingyu Xiao, Shunwang Wang
The Capacitated Location Routing Problem is an important planning and routing problem in logistics, which generalizes the capacitated vehicle routing problem and the uncapacitated…
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…
A Simplified Parameterized Algorithm for Directed Feedback Vertex Set
Ziliang Xiong, Mingyu Xiao
The Directed Feedback Vertex Set problem (DFVS) asks whether it is possible to remove at most vertices from a directed graph to make it acyclic. Whether DFVS is fixed-parameter…
The Traveling Tournament Problem: Improved Algorithms Based on Cycle Packing
Jingyang Zhao, Mingyu Xiao, Chao Xu
The Traveling Tournament Problem (TTP) is a well-known benchmark problem in the field of tournament timetabling, which asks us to design a double round-robin schedule such that eac…
An Improved Approximation Algorithm for Metric Triangle Packing
Jingyang Zhao, Mingyu Xiao
Given an edge-weighted metric complete graph with vertices, the maximum weight metric triangle packing problem is to find a set of vertex-disjoint triangles with the tota…
Approximation Algorithms for Packing Cycles and Paths in Complete Graphs
Jingyang Zhao, Mingyu Xiao
Given an edge-weighted (metric/general) complete graph with vertices, the maximum weight (metric/general) -cycle/path packing problem is to find a set of verte…