All reports by Author Uriel Feige:

__
TR14-110
| 19th August 2014
__

Uriel Feige, Shlomo Jozeph#### Separation between Estimation and Approximation

__
TR14-103
| 8th August 2014
__

Uriel Feige, Michal Feldman, Nicole Immorlica, Rani Izsak, Lucier Brendan, Vasilis Syrgkanis#### A Unifying Hierarchy of Valuations with Complements and Substitutes

__
TR13-095
| 24th June 2013
__

Uriel Feige, Rani Izsak#### Welfare Maximization and the Supermodular Degree

__
TR07-043
| 7th May 2007
__

Uriel Feige, Guy Kindler, Ryan O'Donnell#### Understanding Parallel Repetition Requires Understanding Foams

__
TR06-043
| 22nd March 2006
__

Eran Ofek, Uriel Feige#### Random 3CNF formulas elude the Lovasz theta function

__
TR05-050
| 18th April 2005
__

Uriel Feige, Eran Ofek#### Finding a Maximum Independent Set in a Sparse Random Graph

Revisions: 1

__
TR04-119
| 8th December 2004
__

Uriel Feige, Daniel Reichman#### On The Hardness of Approximating Max-Satisfy

__
TR00-043
| 21st June 2000
__

Uriel Feige, Marek Karpinski, Michael Langberg#### A Note on Approximating MAX-BISECTION on Regular Graphs

__
TR00-021
| 19th April 2000
__

Uriel Feige, Marek Karpinski, Michael Langberg#### Improved Approximation of MAX-CUT on Graphs of Bounded Degree

Uriel Feige, Shlomo Jozeph

We show (under standard assumptions) that there are NP optimization problems for which estimation is easier than approximation. Namely, one can estimate the value of the optimal solution within a ratio of $\rho$, but it is difficult to find a solution whose value is within $\rho$ of optimal.

As an ...
more >>>

Uriel Feige, Michal Feldman, Nicole Immorlica, Rani Izsak, Lucier Brendan, Vasilis Syrgkanis

We introduce a new hierarchy over monotone set functions, that we refer to as $MPH$ (Maximum over Positive Hypergraphs).

Levels of the hierarchy correspond to the degree of complementarity in a given function.

The highest level of the hierarchy, $MPH$-$m$ (where $m$ is the total number of items) captures all ...
more >>>

Uriel Feige, Rani Izsak

Given a set of items and a collection of players, each with a nonnegative monotone valuation set function over the items,

the welfare maximization problem requires that every item be allocated to exactly one player,

and one wishes to maximize the sum of values obtained by the players,

as computed ...
more >>>

Uriel Feige, Guy Kindler, Ryan O'Donnell

Motivated by the study of Parallel Repetition and also by the Unique

Games Conjecture, we investigate the value of the ``Odd Cycle Games''

under parallel repetition. Using tools from discrete harmonic

analysis, we show that after $d$ rounds on the cycle of length $m$,

the value of the game is ...
more >>>

Eran Ofek, Uriel Feige

Let $\phi$ be a 3CNF formula with n variables and m clauses. A

simple nonconstructive argument shows that when m is

sufficiently large compared to n, most 3CNF formulas are not

satisfiable. It is an open question whether there is an efficient

refutation algorithm that for most such formulas proves ...
more >>>

Uriel Feige, Eran Ofek

We consider the problem of finding a maximum independent set in a

random graph. The random graph $G$ is modelled as follows. Every

edge is included independently with probability $\frac{d}{n}$, where

$d$ is some sufficiently large constant. Thereafter, for some

constant $\alpha$, a subset $I$ of $\alpha n$ vertices is ...
more >>>

Uriel Feige, Daniel Reichman

Max-Satisfy is the problem of finding an assignment that satisfies

the maximum number of equations in a system of linear equations

over $\mathbb{Q}$. We prove that unless NP$\subseteq $BPP there is no

polynomial time algorithm for the problem achieving an

approximation ratio of $1/n^{1-\epsilon}$, where $n$ is the number

of ...
more >>>

Uriel Feige, Marek Karpinski, Michael Langberg

We design a $0.795$ approximation algorithm for the Max-Bisection problem

restricted to regular graphs. In the case of three regular graphs our

results imply an approximation ratio of $0.834$.

Uriel Feige, Marek Karpinski, Michael Langberg

We analyze the addition of a simple local improvement step to various known

randomized approximation algorithms.

Let $\alpha \simeq 0.87856$ denote the best approximation ratio currently

known for the Max Cut problem on general graphs~\cite{GW95}.

We consider a semidefinite relaxation of the Max Cut problem,

round it using the ...
more >>>