6 papers · 1 filter
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…