
I am interested in combinatorial optimization problems both in theory and in practice. In particular, part of the focus of my research is on the application of theoretical insights of modern algorithms developed during the last three decades to realworld problems. Of particular interest are those algorithms developed for quickly (polynomial time) obtaining approximate solutions.
Improved approximation schemes for linear programming relaxations of combinatorial optimization problems, with Vania Eleuterio. In IPCO'05, Berlin.
Faster approximation algorithms for minimizing a positive convex and homogeneous function. Manuscript 2004. (This paper contains some obvious extensions of the paper above together with some additional applications not mentioned in the previous paper due to space limitations.)
Improved approximation algorithms for uncapacitated facility location problem, with David Shmoys.
In SIAM Journal on Computing
Fast WDM path protection using precrossconnection, with Tim Chow and Tony Ffrench. In Transactions on Networking.
Approximate kminumum spanning trees and kSteiner trees via the primaldual method and Lagrangean relaxation , with Tim Roughgarden and David Williamson. In Mathematical Programming.
Nearoptimal solutions to large scale facility location problems , with Francisco Barahona. Submitted to Discrete Applied Math.
Solving large scale uncapacitated facility location problems, with Francisco Barahona. In Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems, P. M. Pardalos, Editor, Kluwer Academic Publishers, June, 1999.
Improved approximation algorithms for capacitated facility location problems, with David Williamson. In Proceedings of the 7th Conference on Integer Programming and Combinatorial Optimization, IPCO'99, 99113.
Improved approximation algorithms for uncapacitated facility location. In Proceedings of the Sixth Conference on Integer Programming and Combinatorial Optimization, IPCO'98, 180194.
Improved approximation algorithms for a capacitated facility location problem, with David Shmoys. In Proceedings of the 10th Annual ACMSIAM Symposium on Discrete Algorithms, 875876, 1999.
A 3approximation algorithm for the klevel uncapacitated facility location problem, with Karen Aardal and David Shmoys. In Information Processing Letters 72, 161167, 1999.
Approximation algorithms for precedenceconstrained scheduling problems on parallel machines that run at different speeds, with David Shmoys. In Special Issue of Journal of Algorithms for SODA'97 (only top 10 papers invited) Vol. 30, No. 2, 323343, 1999. A preliminary version appeared in Proceedings of the 8th Annual ACMSIAM Symposium on Discrete Algorithms (1997), 581590.
A primaldual interpretation of 2approximation algorithms for the feedback vertex set problem in undirected graphs, with Michel Goemans, Dorit Hochbaum and David Williamson. In Operations Research Letters 22, 111118, 1998.
A halfintegral linear programming relaxation for scheduling precedenceconstrained jobs on a single machine, with Dorit Hochbaum. In Operations Research Letters 25, 199204, 1999.
A minsum 3/2approximation algorithm for scheduling unrelated parallel machines. In Scheduling 2 (1999), 7377.
"A new extension of Lubell's inequality to the lattice of divisors", with Jerrold R. Griggs. In Studia Scientiarum Mathematiarum Hungarica 35, 347351, 1999.
Wichtiger Hinweis:
Diese Website wird in älteren Versionen von Netscape ohne
graphische Elemente dargestellt. Die Funktionalität der
Website ist aber trotzdem gewährleistet. Wenn Sie diese
Website regelmässig benutzen, empfehlen wir Ihnen, auf
Ihrem Computer einen aktuellen Browser zu installieren. Weitere
Informationen finden Sie auf
folgender
Seite.
Important Note:
The content in this site is accessible to any browser or
Internet device, however, some graphics will display correctly
only in the newer versions of Netscape. To get the most out of
our site we suggest you upgrade to a newer browser.
More
information