ETH Zuerich - Homepage

Dr. Fabian Chudak

Research Interests

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 real-world problems. Of particular interest are those algorithms developed for quickly (polynomial time) obtaining approximate solutions.


Combinatorial Algorithms for Approximately Solving Certain Classes of Large Scale Linear Programs and Applications



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 pre-cross-connection, with Tim Chow and Tony Ffrench. In Transactions on Networking.

Approximate k-minumum spanning trees and k-Steiner trees via the primal-dual method and Lagrangean relaxation , with Tim Roughgarden and David Williamson. In Mathematical Programming.

Near-optimal 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, 99-113.

Improved approximation algorithms for uncapacitated facility location. In Proceedings of the Sixth Conference on Integer Programming and Combinatorial Optimization, IPCO'98, 180-194.

Improved approximation algorithms for a capacitated facility location problem, with David Shmoys. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, 875-876, 1999.

A 3-approximation algorithm for the k-level uncapacitated facility location problem, with Karen Aardal and David Shmoys. In Information Processing Letters 72, 161-167, 1999.

Approximation algorithms for precedence-constrained 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, 323-343, 1999. A preliminary version appeared in Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (1997), 581-590.

A primal-dual interpretation of 2-approximation algorithms for the feedback vertex set problem in undirected graphs, with Michel Goemans, Dorit Hochbaum and David Williamson. In Operations Research Letters 22, 111-118, 1998.

A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine, with Dorit Hochbaum. In Operations Research Letters 25, 199-204, 1999.

A min-sum 3/2-approximation algorithm for scheduling unrelated parallel machines. In Scheduling 2 (1999), 73-77.

"A new extension of Lubell's inequality to the lattice of divisors", with Jerrold R. Griggs. In Studia Scientiarum Mathematiarum Hungarica 35, 347-351, 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

© 2014 Mathematics Department | Imprint | Disclaimer | 22 March 2007