6 citations · 7 across the 4 of their papers we have counts for
4 papers
An Efficient Streaming Algorithm for the Submodular Cover Problem
Ashkan Norouzi-Fard, Abbas Bazzi, Marwa El Halabi +3
We initiate the study of the classical Submodular Cover (SC) problem in the data streaming model which we refer to as the Streaming Submodular Cover (SSC). We show that any single…
Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits
Abbas Bazzi, Samuel Fiorini, Sangxia Huang +1
Initially developed for the min-knapsack problem, the knapsack cover inequalities are used in the current best relaxations for numerous combinatorial optimization problems of cover…
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…
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…