**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Person# Abbas Bazzi

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related units

Loading

Courses taught by this person

Loading

Related research domains

Loading

Related publications

Loading

People doing similar research

Loading

Related publications (10)

Loading

Loading

Loading

Courses taught by this person

People doing similar research (115)

No results

Related research domains (13)

Linear programming relaxation

In mathematics, the relaxation of a (mixed) integer linear program is the problem that arises by removing the integrality constraint of each variable.
For example, in a 0–1 integer program, all cons

Approximation algorithm

In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable

Linear programming

Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented

Related units (3)

Abbas Bazzi, Ola Nils Anders Svensson

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] proved that the problem is NP-hard to approximate within a factor 2- epsilon, 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 inapproximability result for the problem is due to Dinur and Safra [Dinur I, Safra S (2005) On the hardness of approximating minimum vertex cover. Ann. Math. 162(1):439-485]: 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 the vertex cover within a factor 2 - epsilon has super-polynomially many inequalities. As a direct consequence of our methods, we also establish that LP relaxations (as well as semidefinite programming relaxations) that approximate the independent set problem within any constant factor have a super-polynomial size.

Abbas Bazzi, Sangxia Huang, Ola Nils Anders 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 epsilon > 0, there is a (1/epsilon)(o(1))n(o(log n))- size LP relaxation with an integrality gap of at most 2 +epsilon, where n is the number of items. Previously, there was no known relaxation of subexponential size with a constant upper bound on the integrality gap. Our techniques are also sufficiently versatile to give analogous results for the closely related flow cover inequalities that are used to strengthen relaxations for scheduling and facility location problems.