Publications: [Papers] [Thesis]
-
Approximation algorithms for partially covering with edges.
Accepted to Theoretical Computer Science, 2008.
Emory University Math/CS department technical report TR-2007-018.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
Edge dominating and hypomatchable sets
[ps].
Appears in the proceedings of the Symposium on Discrete Algorithms, 2002, pp. 287-291.
-
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.
-
Forestation in Hypergraphs: Linear k-Trees [pdf].
The Electronic Journal of Combinatorics. 10 (2003), No. 1, #N12.
-
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.
-
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.
-
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:
-
Polyhedral Techniques for Graphic Covering Problems
[ps.gz].
Submitted to the Algorithms, Combinatorics, and Optimization program at Carnegie Mellon University, 2002.