Jingyang Zhao

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 $(1 + 1/ 2)$ -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 $n$ vertices and non-negative edge weights, where $n$ is divisible by 3, the maximum weight 3-path packing problem is to find a set of $n /3$ 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 $n$ -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…

cs.DS2024

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…

cs.DS2024

An Improved Approximation Algorithm for Metric Triangle Packing

Jingyang Zhao, Mingyu Xiao

Given an edge-weighted metric complete graph with $n$ vertices, the maximum weight metric triangle packing problem is to find a set of $n /3$ 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 $n$ vertices, the maximum weight (metric/general) $k$ -cycle/path packing problem is to find a set of $\frac{n}{k}$ verte…

A $5$ -approximation Algorithm for the Traveling Tournament Problem

Jingyang Zhao, Mingyu Xiao

The Traveling Tournament Problem (TTP- $k$ ) is a well-known benchmark problem in tournament timetabling, which asks us to design a double round-robin schedule such that the total tr…

Multidepot Capacitated Vehicle Routing with Improved Approximation Guarantees

Jingyang Zhao, Mingyu Xiao

The Multidepot Capacitated Vehicle Routing Problem (MCVRP) is a well-known variant of the classic Capacitated Vehicle Routing Problem (CVRP), where we need to route capacitated veh…