6 citations · 11 across the 8 of their papers we have counts for
9 papers
Breaking the Barrier for Maximum Weighted -Set Packing
Weitian Tong, Yao Xu
We give a deterministic polynomial-time -approximation for Maximum Weighted -Set Packing, breaking the locality-gap barrier of squared-weight local search. The…
Cross-Shift Analysis for Unrelated-Machine Weighted Completion Time A (1.3168+epsilon)-Approximation
Weitian Tong, Yao Xu
We study the problem of minimizing total weighted completion time on unrelated parallel machines with machine-independent job weights. The best previous approximation guarantee for…
Random-Order Enumeration for Self-Reducible NP-Problems
Pengyu Chen, Dongjing Miao, Weitian Tong +3
In plenty of data analysis tasks, a basic and time-consuming process is to produce a large number of solutions and feed them into downstream processing. Various enumeration algorit…
An efficient polynomial-time approximation scheme for parallel multi-stage open shops
Jianming Dong, Ruyan Jin, Guohui Lin +3
Various new scheduling problems have been arising from practical production processes and spawning new research areas in the scheduling field. We study the parallel multi-stage ope…
A polynomial-time approximation scheme for parallel two-stage flowshops under makespan constraint
Weitian Tong, Yao Xu, Huili Zhang
As a hybrid of the Parallel Two-stage Flowshop problem and the Multiple Knapsack problem, we investigate the scheduling of parallel two-stage flowshops under makespan constraint, w…
A local search -approximation algorithm for the minimum -path partition problem
Yong Chen, Randy Goebel, Guohui Lin +5
Given a graph , the -path partition problem is to find a minimum collection of vertex-disjoint paths each of order at most to cover all the vertices of . It i…
Single machine scheduling with job-dependent machine deterioration
Wenchang Luo, Yao Xu, Weitian Tong +1
We consider the single machine scheduling problem with job-dependent machine deterioration. In the problem, we are given a single machine with an initial non-negative maintenance l…
An approximation algorithm for the Bandpass-2 problem
Weitian Tong, Zhi-Zhong Chen, Lusheng Wang +4
The general Bandpass- problem is NP-hard and can be approximated by a reduction into the weighted -set packing problem, with a worst case performance ratio of . When…
Algorithms for Cut Problems on Trees
Iyad Kanj, Guohui Lin, Tian Liu +7
We study the {\sc multicut on trees} and the {\sc generalized multiway Cut on trees} problems. For the {\sc multicut on trees} problem, we present a parameterized algorithm that ru…