2 citations · 3 across the 14 of their papers we have counts for
4 papers · 1 filter
Inapproximability of Unique-Machine Precedence Scheduling for Unit-Length Jobs
Venkatesan Guruswami, Xuandi Ren, Shaoxuan Tang
The Unique-Machine Precedence Scheduling (UMPS) problem, introduced by [DKRSTZ22], seeks a makespan-minimizing schedule of precedence-constrained jobs when each job has a unique el…
Scheduling Problems with Constrained Rejections
Sami Davies, Venkatesan Guruswami, Xuandi Ren
We study bicriteria versions of Makespan Minimization on Unrelated Machines and Santa Claus by allowing a constrained number of rejections. Given an instance of Makespan Minimizati…
Constant Approximating Parameterized -SetCover is W[2]-hard
Bingkai Lin, Xuandi Ren, Yican Sun +1
In this paper, we prove that it is W[2]-hard to approximate k-SetCover within any constant ratio. Our proof is built upon the recently developed threshold graph composition techniq…
Generalized Sorting with Predictions
Pinyan Lu, Xuandi Ren, Enze Sun +1
Generalized sorting problem, also known as sorting with forbidden comparisons, was first introduced by Huang et al. together with a randomized algorithm which requires $\tilde O(n^…