Author name cluster

Abbas Bazzi

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

2 author rows

SODA Conference 2017 Conference Paper

Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits

Abbas Bazzi
Samuel Fiorini
Sangxia Huang
Ola Svensson

Initially developed for the min-knapsack problem, the knapsack cover inequalities are used in the current best relaxations for numerous combinatorial optimization problems of covering type. In spite of their widespread use, these inequalities yield linear programming (LP) relaxations of exponential size, over which it is not known how to optimize exactly in polynomial time. In this paper we address this issue and obtain LP relaxations of quasi-polynomial size that are at least as strong as that given by the knapsack cover inequalities. For the min-knapsack cover problem, our main result can be stated formally as follows: for any ∊ > 0, there is a (1/∊) O (1) n O (log n ) -size LP relaxation with an integrality gap of at most 2 + ∊, where n is the number of items. Prior to this work, there was no known relaxation of subexponential size with a constant upper bound on the integrality gap. Our construction is inspired by a connection between extended formulations and monotone circuit complexity via Karchmer-Wigderson games. In particular, our LP is based on O (log 2 n )-depth monotone circuits with fan-in 2 for evaluating weighted threshold functions with n inputs, as constructed by Beimel and Weinreb. We believe that a further understanding of this connection may lead to more positive results complementing the numerous lower bounds recently proved for extended formulations.

Details

NeurIPS Conference 2016 Conference Paper

An Efficient Streaming Algorithm for the Submodular Cover Problem

Ashkan Norouzi-Fard
Abbas Bazzi
Ilija Bogunovic
Marwa El Halabi
Ya-Ping Hsieh
Volkan Cevher

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 pass streaming algorithm using sublinear memory in the size of the stream will fail to provide any non-trivial approximation guarantees for SSC. Hence, we consider a relaxed version of SSC, where we only seek to find a partial cover. We design the first Efficient bicriteria Submodular Cover Streaming (ESC-Streaming) algorithm for this problem, and provide theoretical guarantees for its performance supported by numerical evidence. Our algorithm finds solutions that are competitive with the near-optimal offline greedy algorithm despite requiring only a single pass over the data stream. In our numerical experiments, we evaluate the performance of ESC-Streaming on active set selection and large-scale graph cover problems.

PDF Details

FOCS Conference 2015 Conference Paper

No Small Linear Program Approximates Vertex Cover within a Factor 2 - e

Abbas Bazzi
Samuel Fiorini
Sebastian Pokutta
Ola Svensson

The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev [30], [31] proved that the problem is NP-hard to approximate within a factor 2 - ε, assuming the Unique Games Conjecture (UGC). This is tight because the problem has an easy 2-approximation algorithm. Without resorting to the UGC, the best in approximability result for the problem is due to Dinur and Safra [16], [17]: vertex cover is NP-hard to approximate within a factor 1. 3606. We prove the following unconditional result about linear programming (LP) relaxations of the problem: every LP relaxation that approximates vertex cover within a factor of 2 - ε has super-polynomially many inequalities. As a direct consequence of our methods, we also establish that LP relaxations (as well as SDP relaxations) that approximate the independent set problem within any constant factor have super-polynomially many inequalities.

Details