Publications 2005-2007

Uriel Feige, Kamal Jain, Mohammad Mahdian, Vahab Mirrokni.
Robust Combinatorial Optimization with Exponential Scenarios.
IPCO 2007: 439-453.
Version: November 2006.

Uriel Feige and Daniel Reichman.
On the Hardness of Approximating Max-Satisfy.
Inf. Process. Lett. 97(1): 31-35 (2006).
Version: September 2006.

Uriel Feige and Mohit Singh.
Improved approximation ratios for traveling salesperson tours and paths in directed graphs.
APPROX-RANDOM 2007: 104-118.
Version: August 2006.

Uriel Feige, Jeong Han Kim, Eran Ofek.
Witnesses for non-satisfiability of dense random 3CNF formulas.
FOCS 2006: 497-508.
Version: May 2006.

Uriel Feige and Eran Ofek.
Random 3CNF formulas elude the Lovasz theta function.
ECCC 13(043).
Version: April 2006.

Uriel Feige and Mohammad Mahdian.
Finding small balanced separators.
STOC 2006: 375-384.
Version: March 2006.

Uriel Feige and Jan Vondrak.
The allocation problem with submodular utility functions.
Later version: The Submodular Welfare Problem with Demand Queries. Theory of Computing 6(1): 247-290 (2010).
Version: February 2006.

Uriel Feige and James Lee.
An improved approximation ratio for the minimum linear arrangement problem.
Inf. Process. Lett. 101(1): 26-29 (2007).
Version: January 2006.

Erik Demaine, Uriel Feige, MohammadTaghi Hajiaghayi, Mohammad Salavatipour.
Combination Can Be Hard: Approximability of the Unique Coverage Problem.
SIAM J. Comput. 38(4): 1464-1483 (2008).
Version: October 2005.

Uriel Feige, MohammadTaghi Hajiaghayi, James R. Lee.
Improved approximation algorithms for minimum-weight vertex separators.
SIAM J. Comput. 38(2): 629-657 (2008).
Version: October 2005.

Uriel Feige, Abraham Flaxman, Jason Hartline, Robert Kleinberg.
On the Competitive Ratio of the Random Sampling Auction.
WINE 2005: 878-886.
Version: September 2005.

Uriel Feige and Kunal Talwar.
Approximating the Bandwidth of Caterpillars.
Algorithmica 55(1): 190-204 (2009).
Version: June 2005.

Uriel Feige.
Rigorous Analysis of Heuristics for NP-hard Problems.
Invited talk SODA 2005.
Version: January 2005.