Julian Mestre

BE UCA MSc PhD UMD
ARC Discovery Early Career Researcher

Contact Information

Office: School of IT, J12. Room 4W-410.
Phone: +61 2 9351 4276
Email: reveal email address

Research Interests

I am broadly interested in the design and analysis of efficient algorithms for combinatorial optimization problems such as:

• Approximation algorithms for covering, packing, coloring, scheduling, and routing problems.
• Matchings under preferences: popular, stable and fair assignments.
• Uncertainty models: universal, incremental, and stochastic optimization.

Selected Publications

• On Tree-Constrained Matchings and Generalizations with S. Canzar, K. Elbassioni, and G. Klau
  ICALP 2011
• When LP is the Cure for Your Matching Woes with Bansal, Gupta, Li, Nagarajan and Rudra
  Algorithmica and ESA 2010 (best paper award)
• Universal sequencing on a single machine with Epstein, Levin, Marchetti-Spaccamela, Megow, Skutella, and Stougie
  SIAM J. on Computing and IPCO 2010
• Popular mixed matchings with Telikepalli, and Nasre
  Theoretical Computer Science and ICALP 2009
• Lagrangian Relaxation and Partial Cover
  STACS 2008
• Adaptive Local Ratio
  SIAM J. on Computing and SODA 2008 (best student paper award)

For a complete list, see my publications page.