Publications: [Papers] [Thesis]
  1. Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees [pdf],
    with J. Könemann and D. Pritchard.
    To appear in the proceedings of the Workshop on Approximation and Online Algorithms (WAOA), 2008.

  2. Approximation algorithms for partially covering with edges [doi].
    Theoretical Computer Science, 400(1-3), pp. 159-168, 2008.

  3. 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. 43-52, 2007.

  4. 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. 468-479, 2006.

  5. 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. 564-575, 2006.

  6. Capacitated b-Edge Dominating Set and Related Problems [doi],
    with A. Berger, T. Fukunaga, and H. Nagamochi.
    Theoretical Computer Science. 385(1-3), pp. 202-213, 2007.

  7. Linear Time Algorithms for Generalized Edge Dominating Set Problems [doi],
    with A. Berger.
    Algorithmica. 50(2), pp. 244-254, 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. 233-243, 2005.

  8. Finding Effective Support-Tree 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. 176-185, 2005.

  9. A 1/2-Integral Relaxation for the A-Matching Problem [doi],
    with R. Carr.
    Operations Research Letters. 34(4), pp. 445-450, 2006.

  10. On Factor Width and Symmetric H-matrices [doi],
    with E. G. Boman, D. Chen, and S. Toledo.
    Linear Algerbra and Its Applications. 405, pp. 239-248, 2005.

  11. 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. 649-661, 2002.

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

  13. An approximation algorithm for edge-dilation k-center problem [doi],
    with J. Könemann, Y. Li, and A. Sinha.
    Operations Research Letters. 32(5), pp. 491-495, 2004.
    A preliminary version appears in the proceedings of the Scandinavian Workshop on Algorithmic Theory (SWAT), pp. 210-219, 2002.

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

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

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

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

My thesis: