Publications: [Papers] [Thesis]

MaxWeight Integral Multicommodity Flow in Spiders and HighCapacity Trees
[pdf],
with J. Könemann and
D. Pritchard.
To appear in the proceedings of the Workshop on Approximation and Online Algorithms (WAOA), 2008.

Approximation algorithms for partially covering with edges
[doi].
Theoretical Computer Science, 400(13), pp. 159168, 2008.

Compacting cuts: a new linear formulation for minimum cut
[pdf],
with R. Carr,
G. Konjevod,
G. Little,
and V. Natarajan.
Accepted for publication in a special issue of the ACM Transactions on Algorithms dedicated to selected
papers from SODA 2007.
A preliminary version appears in the proceedings of the Symposium on Discrete Algorithms (SODA), pp. 4352, 2007.

A Unified Approach to Approximating Partial Covering Problems
[pdf],
J. Könemann and
D. Segev.
Appears in the proceedings of the European Symposium on Algorithms (ESA), pp. 468479, 2006.

Path Hitting in Acyclic Graphs
[doi],
with D. Segev.
To appear in Algorithmica, 2008.
A preliminary version appears in the proceedings of the European Symposium on Algorithms (ESA), pp. 564575, 2006.

Capacitated bEdge Dominating Set and Related Problems
[doi],
with A. Berger,
T. Fukunaga, and
H. Nagamochi.
Theoretical Computer Science. 385(13), pp. 202213, 2007.

Linear Time Algorithms for Generalized Edge Dominating Set Problems
[doi],
with A. Berger.
Algorithmica. 50(2), pp. 244254, 2008.
Appears in a special issue dedicated to select papers invited from WADS 2005.
A preliminary version appears in the proceedings of the Workshop on Algorithms and Data Structures (WADS), pp. 233243, 2005.

Finding Effective SupportTree Preconditioners
[pdf],
with B. Maggs,
G. Miller,
R. Ravi, and
S.L. Woo.
Appears in the proceedings of the Syposium of Parallel Architectures and Algorithms (SPAA), pp. 176185, 2005.

A 1/2Integral Relaxation for the AMatching Problem
[doi],
with R. Carr.
Operations Research Letters. 34(4), pp. 445450, 2006.

On Factor Width and Symmetric Hmatrices
[doi],
with E. G. Boman,
D. Chen, and
S. Toledo.
Linear Algerbra and Its Applications. 405, pp. 239248, 2005.

Randomized Approximation Algorithms for Query Optimization on Two Processors
[pdf],
with E. Laber and
R. Ravi.
Appears in the proceedings of the European Symposium on Algorithms (ESA), pp. 649661, 2002.

Edge dominating and hypomatchable sets
[ps].
Appears in the proceedings of the Symposium on Discrete Algorithms (SODA), pp. 287291, 2002.

An approximation algorithm for edgedilation kcenter problem
[doi],
with J. Könemann,
Y. Li, and
A. Sinha.
Operations Research Letters. 32(5), pp. 491495, 2004.
A preliminary version appears in the proceedings of the Scandinavian Workshop on Algorithmic Theory (SWAT), pp. 210219, 2002.

Forestation in Hypergraphs: Linear kTrees [pdf].
The Electronic Journal of Combinatorics. 10(1), #N12, 2003.

Improved Approximations for Tour and Tree Covers
[doi],
with J. Könemann,
G. Konjevod, and
A. Sinha.
Algorithmica. 38(3), pp. 441449, 2003.
A preliminary in the proceedings of Approximation Algorithms for Combinatorial Optimization (APPROX), pp. 184193, 2000.

A 2 1/10Approximation Algorithm for a Generalization of the Weighted EdgeDominating Set Problem
[ps],
with R. Carr,
T. Fujito, and
G. Konjevod.
Journal of Combinatorial Optimization. 5(3), pp. 317326, 2001.
A preliminary version appears in the proceedings of the European Symposium of Algorithms (ESA), pp. 317326, 2000.

A Survey and New Results in Renegotiated Service,
with E. Zegura and
S. McFarland.
Journal of High Speed Networks. 6(3), 1997.
My thesis: