approximation hardness 1communication delays 1hypergraph coloring 1precedence constraints 1scheduling 1
From the 1 of 2 linked papers with an AI index.
2 papers
cs.DS2026
Inapproximability of Unique-Machine Precedence Scheduling for Unit-Length Jobs
Venkatesan Guruswami, Xuandi Ren, Shaoxuan Tang
The paper shows that scheduling unit-length jobs with unique-machine precedence constraints cannot be approximated within any constant factor, and under standard complexity assumpt…
cs.CC2026
Strong Inapproximability for a Promise Rank Problem
Venkatesan Guruswami, Xuandi Ren, Shaoxuan Tang
Given a linear subspace of matrices over that is promised to contain a matrix of rank , we prove that it is hard to find a matrix of rank $n^{o(1/…