Publications: [Papers] [Thesis]
  1. Approximation algorithms for partially covering with edges.
    Accepted to Theoretical Computer Science, 2008.
    Emory University Math/CS department technical report TR-2007-018.

  2. Compacting cuts: a new linear formulation for minimum cut [pdf].
    with R. Carr, G. Konjevod, G. Little, and V. Natarajan
    Appears in the proceedings of the Symposium on Discrete Algorithms, 2007, pp. 43-52.
    Accepted for publication in a special issue of the ACM Transactions on Algorithms dedicated to selected papers from SODA 2007.

  3. A Unified Approach to Approximating Partial Covering Problems [pdf].
    with J. Könemann and D. Segev
    Appears in the proceedings of the European Symposium on Algorithms, 2006, pp. 468-479.

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

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

  6. Linear Time Algorithms for Generalized Edge Dominating Set Problems [doi].
    with A. Berger.
    Algorithmica. 50 (2008), No. 2, pp. 244-254.
    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, 2005, pp. 233-243.
    Emory University Math/CS department technical report TR-2005-002-A.

  7. 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, 2005, pp. 176-185.
    Emory University Math/CS department technical report TR-2005-003-A.

  8. A 1/2-Integral Relaxation for the A-Matching Problem [doi].
    with R. Carr.
    Operations Research Letters. 34 (2006), No. 4, pp. 445-450.
    Emory University Math/CS department technical report TR-2005-001-A.

  9. On Factor Width and Symmetric H-matrices [doi].
    with E.G. Boman, D. Chen, and S. Toledo.
    Linear Algerbra and Its Applications. 405 (2005), pp. 239-248.
    Emory University Math/CS department technical report TR-2005-004-A.

  10. 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, 2002, pp. 649-661.
    Journal version in preparation, 2005.

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

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

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

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

  15. 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 (2001), No. 3, pp. 317-326.
    A preliminary version appears in the proceedings of the European Symposium of Algorithms, 2000, pp. 317-326.

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

My thesis: