6 citations · 7 across the 4 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2015
Towards Tight Lower Bounds for Scheduling Problems
Abbas Bazzi, Ashkan Norouzi-Fard
We show a close connection between structural hardness for -partite graphs and tight inapproximability results for scheduling problems with precedence constraints. Assuming a na…
cs.CC2015★ 1 cited
No Small Linear Program Approximates Vertex Cover within a Factor
Abbas Bazzi, Samuel Fiorini, Sebastian Pokutta +1
The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev (2003) proved that the problem is NP-hard to appro…