Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Home

Person

Abbas Bazzi

This person has left EPFL

About
Privacy
Disclaimer

Graph Chatbot

Related publications (5)

Page 1 of 1

Strengths and Limitations of Linear Programming Relaxations

Abbas Bazzi

Many of the currently best-known approximation algorithms for NP-hard optimization problems are based on Linear Programming (LP) and Semi-definite Programming (SDP) relaxations. Given its power, this class of algorithms seems to contain the most favourable ...

EPFL2017

Towards Tight Lower Bounds for Scheduling Problems

Ashkan Norouzi Fard, Abbas Bazzi

We show a close connection between structural hardness for k-partite graphs and tight inapproximability results for scheduling problems with precedence constraints. Assuming a natural but nontrivial generalisation of the bipartite structural hardness resul ...

Springer Int Publishing Ag2015

No Small Linear Program Approximates Vertex Cover Within a Factor 2-epsilon

Ola Nils Anders Svensson, Abbas Bazzi

The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev [Khot S, Regev O (2008) Vertex cover might be hard to approximate to within 2 - epsilon. J. Comput. System Sci. 74(3): 335-349 ...

INFORMS2019

Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits

Ola Nils Anders Svensson, Abbas Bazzi

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 ...

UNIV CHICAGO, DEPT COMPUTER SCIENCE2018

An Efficient Streaming Algorithm for the Submodular Cover Problem

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

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 wi ...

2016