Dr Julian Mestre

BEUCA MSs PhD UMD
ARC Discovery Early Career Research Fellow
Senior Lecturer in Large Scale Convex Optimization
School of Information Technologies

J12 - The School of Information Technologies
The University of Sydney

Telephone +61 2 9351 4276
Fax +61 2 9351 3838

Website School of Information Technologies

Biographical details

Dr Julian Mestre is a Senior Lecturer in the School of Information Technologies. Before joining the University of Sydney, he was a postdoctoral fellow at the Max Planck Institute for Informatics in Germany. He has a PhD in Computer Science from the University of Maryland in the United States.

Julian's main area of research is Theoretical Computer Science. He is broadly interested in the design and analysis of efficient algorithms for combinatorial optimization problems such as covering, scheduling, routing and matching problems.

Teaching and supervision

COMP3530 - Discrete Optimization

INFO1911 - IT Special Project 1A

INFO1912 - IT Special Project 1B

INFO2911 - IT Special Project 2A

INFO2912 - IT Special Project 2B

INFO3911 - IT Special Project 3A

INFO3912 - IT Special Project 3B

Selected grants

2015

  • Local reoptimization for turbocharging heuristics; Gudmundsson J, Fellows M, Gaspers S, Mestre J, Fomin F; Australian Research Council (ARC)/Discovery Projects (DP).

2013

  • Universal solutions for scheduling problems; Mestre J; Australian Research Council (ARC)/Discovery Early Career Researcher Award (DECRA).
  • Algorithms for Combinatorial Optimization Problems on Uncertain Inputs; Mestre J; Group of Eight/Germany Joint Research Co-operation Scheme.

Selected publications

Download citations: PDF RTF Endnote

Journals

  • Mestre, J. (2014). A Primal-Dual Approximation Algorithm for Partial Vertex Cover: Making Educated Guesses. Algorithmica: an international journal in computer science, 55, 227-239. [More Information]
  • Gandhi, R., Mestre, J. (2014). Combinatorial Algorithms for Data Migration to Minimize Average Completion Time. Algorithmica: an international journal in computer science, 54(1), 54-71. [More Information]
  • Aziz, H., Brandt, F., Brill, M., Mestre, J. (2014). Computational aspects of random serial dictatorship. ACM SIGecom Exchanges, 13(2), 26-30. [More Information]
  • Hoehn, W., Mestre, J., Wiese, A. (2014). How Unsplittable-Flow-Covering Helps Scheduling with Job-Dependent Cost Functions. Lecture Notes in Computer Science (LNCS), 8572 (Part 1), 625-636. [More Information]
  • Thilakarathna, K., Petander, H., Mestre, J., Seneviratne, A. (2014). MobiTribe: Cost Efficient Distributed User Generated Content Sharing on Smartphones. IEEE Transactions on Mobile Computing, 13(9), 2058-2070. [More Information]
  • Hermelin, D., Mestre, J., Rawitz, D. (2014). Optimization problems in dotted interval graphs. Discrete Applied Mathematics, 174, 66-72. [More Information]
  • Manshadi, F., Awerbuch, B., Gemulla, R., Khandekar, R., Mestre, J., Sozio, M. (2013). A distributed algorithm for large-scale generalized matching. Proceedings of the VLDB Endowment, 6(9), 613-624.
  • Kavitha, T., Mestre, J. (2012). Max-coloring paths: tight bounds and extensions. Journal of Combinatorial Optimization, 24(1), 1-14. [More Information]
  • Hajiaghayi, M., Khandekar, R., Kortsarz, G., Mestre, J. (2012). The checkpoint problem. Theoretical Computer Science, 452, 88-99. [More Information]
  • Epstein, L., Levin, A., Marchetti-Spaccamela, A., Megow, N., Mestre, J., Skutella, M., Stougie, L. (2012). Universal Sequencing on an Unreliable Machine. SIAM Journal on Computing, 41(3), 565-586. [More Information]
  • Bansal, N., Gupta, A., Li, J., Mestre, J., Nagarajan, V., Rudra, A. (2012). When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings. Algorithmica: an international journal in computer science, 63(4), 733-762. [More Information]
  • Mestre, J., Althaus, E., Canzar, S., Elbassioni, K., Karrenbauer, A. (2011). Approximation Algorithms for the Interval Constrained Coloring Problem. Algorithmica: an international journal in computer science, 61(2), 342-361. [More Information]
  • Epstein, L., Levin, A., Mestre, J., Segev, D. (2011). Improved Approximation Guarantees for Weighted Matching in the Semi-Streaming Model. SIAM Journal on Discrete Mathematics, 25(3), 1251-1265. [More Information]
  • Schelhorn, S., Mestre, J., Albrecht, M., Zotenko, E. (2011). Inferring Physical Protein Contacts from Large-Scale Purification Data of Protein Complexes. Molecular and Cellular Proteomics, 10(6), 1-15. [More Information]
  • Khuller, S., Malekian, A., Mestre, J. (2011). To Fill or Not to Fill: The Gas Station Problem. ACM Transactions on Algorithms, 7(3), 36:1-36:16. [More Information]
  • Bar-Yehuda, R., Flysher, G., Mestre, J., Rawitz, D. (2010). Approximation of Partial Capacitated Vertex Cover. SIAM Journal on Discrete Mathematics, 24(4), 1441-1469. [More Information]
  • Garg, N., Kavitha, T., Kumar, A., Mehlhorn, K., Mestre, J. (2010). Assigning Papers to Referees. Algorithmica: an international journal in computer science, 58(1), 119-136. [More Information]
  • Epstein, L., Kleiman, E., Mestre, J. (2009). Parametric Packing of Selfish Items and the Subset Sum Algorithm. Lecture Notes in Computer Science (LNCS), 5929, 67-78.
  • Althaus, E., Canzar, S., Elbassioni, K., Karrenbauer, A., Mestre, J. (2008). Approximating the Interval Constrained Coloring Problem. Lecture Notes in Computer Science (LNCS), 5124, 210-221. [More Information]
  • Zotenko, E., Mestre, J., O'Leary, D., Przytycka, T. (2008). Why Do Hubs in the Yeast Protein Interaction Network Tend To Be Essential: Reexamining the Connection between the Network Topology and Essentiality. PLoS Computational Biology, 4(8), e1000140-1-e1000140-16. [More Information]
  • Mestre, J. (2006). On the multi-radius cover problem. Information Processing Letters, 99(6), 195-198. [More Information]

Conferences

  • Megow, N., Mestre, J. (2013). Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints. 4th ACM Conference on Innovations in Theoretical Computer Science (ITCS 2013), Berkeley, United States: Association for Computing Machinery (ACM). [More Information]
  • Thilakarathna, K., Petander, H., Mestre, J., Seneviratne, A. (2012). Enabling Mobile Distributed Social Networking on Smartphones. The 15th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM12), New York: Association for Computing Machinery (ACM). [More Information]
  • Hermelin, D., Mestre, J., Rawitz, D. (2012). Optimization Problems in Dotted Interval Graphs. 38th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2012), Heidelberg: Springer. [More Information]
  • Canzar, S., Elbassioni, K., Klau, G., Mestre, J. (2011). On Tree-Constrained Matchings and Generalizations. 38th International Colloquium on Automata, Languages and Programming, ICALP 2011, Heidelberg, Germany: Springer. [More Information]
  • Canzar, S., Elbassioni, K., Mestre, J. (2010). A Polynomial Delay Algorithm for Enumerating Approximate Solutions to the Interval Constrained Coloring Problem. 12th Workshop on Algorithm Engineering and Experiments 2010 (ALENEX10), United States of America: Society for Industrial and Applied Mathematics (SIAM).
  • Seufert, S., Bedathur, S., Mestre, J., Weikum, G. (2010). Bonsai: Growing Interesting Small Trees. 10th IEEE International Conference on Data Mining (ICDM 2010), USA: (IEEE) Institute of Electrical and Electronics Engineers. [More Information]
  • Epstein, L., Levin, A., Mestre, J., Segev, D. (2010). Improved Approximation Guarantees for Weighted Matching in the Semi-Streaming Model. [More Information]
  • Hajiaghayi, M., Khandekar, R., Kortsarz, G., Mestre, J. (2010). The Checkpoint Problem. 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2010), Germany: Springer.
  • Epstein, L., Levin, A., Marchetti-Spaccamela, A., Megow, N., Mestre, J., Skutella, M., Stougie, L. (2010). Universal Sequencing on a Single Machine. 14th Conference on Integer Programming and Combinatorial Optimization (IPCO XIV) 2010, Berlin: Springer.
  • Bansal, N., Gupta, A., Li, J., Mestre, J., Nagarajan, V., Rudra, A. (2010). When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings (Extended Abstract). 18th Annual European Symposium on Algorithms ESA 2010 (ALGO 2010), Berlin: Springer.
  • Elbassioni, K., Krohn, E., Matijevic, D., Mestre, J., Severdija, D. (2009). Improved Approximations for Guarding 1.5-Dimensional Terrains. 26th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2009), Freiburg: IBFI Schloss Dagstuhl.
  • Kavitha, T., Mestre, J. (2009). Max-Coloring Paths: Tight Bounds and Extensions. 20th International Symposium on Algorithms and Computation ISAAC 2009, Germany: Springer.
  • Kavitha, T., Mestre, J., Nasre, M. (2009). Popular Mixed Matchings. 36th International Colloquium on Automata, Languages and Programming (ICALP 2009), Germany: Springer.
  • Mestre, J. (2008). Adaptive Local Ratio. 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008), Philadelphia: Society for Industrial and Applied Mathematics (SIAM).
  • Khuller, S., Mestre, J. (2008). An Optimal Incremental Algorithm for Minimizing Lateness with Rejection. 16th Annual European Symposium on Algorithms ESA 2008, Germany: Springer.
  • Mestre, J. (2008). Lagrangian Relaxation and Partial Cover. 25th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2008), Leibniz: IBFI Schloss Dagstuhl.
  • Bar-Yehuda, R., Flysher, G., Mestre, J., Rawitz, D. (2007). Approximation of Partial Capacitated Vertex Cover. 15th Annual European Symposium on Algorithms ESA 2007, Germany: Springer.
  • Khuller, S., Malekian, A., Mestre, J. (2007). To Fill or Not to Fill: The Gas Station Problem. 15th Annual European Symposium on Algorithms ESA 2007, Germany: Springer.
  • Gandhi, R., Mestre, J. (2006). Combinatorial Algorithms for Data Migration to Minimize Average Completion Time. 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2006), Germany: Springer.
  • Mestre, J. (2006). Greedy in Approximation Algorithms. 14th Annual European Symposium on Algorithms ESA 2006, Germany: Springer.
  • Mestre, J. (2006). Weighted Popular Matchings. 33rd International Colloquium on Automata, Languages and Programming (ICALP 2006), Germany: Springer.
  • Mestre, J. (2005). A Primal-Dual Approximation Algorithm for Partial Vertex Cover: Making Educated Guesses. 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2005), Germany: Springer.

2014

  • Mestre, J. (2014). A Primal-Dual Approximation Algorithm for Partial Vertex Cover: Making Educated Guesses. Algorithmica: an international journal in computer science, 55, 227-239. [More Information]
  • Gandhi, R., Mestre, J. (2014). Combinatorial Algorithms for Data Migration to Minimize Average Completion Time. Algorithmica: an international journal in computer science, 54(1), 54-71. [More Information]
  • Aziz, H., Brandt, F., Brill, M., Mestre, J. (2014). Computational aspects of random serial dictatorship. ACM SIGecom Exchanges, 13(2), 26-30. [More Information]
  • Hoehn, W., Mestre, J., Wiese, A. (2014). How Unsplittable-Flow-Covering Helps Scheduling with Job-Dependent Cost Functions. Lecture Notes in Computer Science (LNCS), 8572 (Part 1), 625-636. [More Information]
  • Thilakarathna, K., Petander, H., Mestre, J., Seneviratne, A. (2014). MobiTribe: Cost Efficient Distributed User Generated Content Sharing on Smartphones. IEEE Transactions on Mobile Computing, 13(9), 2058-2070. [More Information]
  • Hermelin, D., Mestre, J., Rawitz, D. (2014). Optimization problems in dotted interval graphs. Discrete Applied Mathematics, 174, 66-72. [More Information]

2013

  • Manshadi, F., Awerbuch, B., Gemulla, R., Khandekar, R., Mestre, J., Sozio, M. (2013). A distributed algorithm for large-scale generalized matching. Proceedings of the VLDB Endowment, 6(9), 613-624.
  • Megow, N., Mestre, J. (2013). Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints. 4th ACM Conference on Innovations in Theoretical Computer Science (ITCS 2013), Berkeley, United States: Association for Computing Machinery (ACM). [More Information]

2012

  • Thilakarathna, K., Petander, H., Mestre, J., Seneviratne, A. (2012). Enabling Mobile Distributed Social Networking on Smartphones. The 15th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM12), New York: Association for Computing Machinery (ACM). [More Information]
  • Kavitha, T., Mestre, J. (2012). Max-coloring paths: tight bounds and extensions. Journal of Combinatorial Optimization, 24(1), 1-14. [More Information]
  • Hermelin, D., Mestre, J., Rawitz, D. (2012). Optimization Problems in Dotted Interval Graphs. 38th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2012), Heidelberg: Springer. [More Information]
  • Hajiaghayi, M., Khandekar, R., Kortsarz, G., Mestre, J. (2012). The checkpoint problem. Theoretical Computer Science, 452, 88-99. [More Information]
  • Epstein, L., Levin, A., Marchetti-Spaccamela, A., Megow, N., Mestre, J., Skutella, M., Stougie, L. (2012). Universal Sequencing on an Unreliable Machine. SIAM Journal on Computing, 41(3), 565-586. [More Information]
  • Bansal, N., Gupta, A., Li, J., Mestre, J., Nagarajan, V., Rudra, A. (2012). When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings. Algorithmica: an international journal in computer science, 63(4), 733-762. [More Information]

2011

  • Mestre, J., Althaus, E., Canzar, S., Elbassioni, K., Karrenbauer, A. (2011). Approximation Algorithms for the Interval Constrained Coloring Problem. Algorithmica: an international journal in computer science, 61(2), 342-361. [More Information]
  • Epstein, L., Levin, A., Mestre, J., Segev, D. (2011). Improved Approximation Guarantees for Weighted Matching in the Semi-Streaming Model. SIAM Journal on Discrete Mathematics, 25(3), 1251-1265. [More Information]
  • Schelhorn, S., Mestre, J., Albrecht, M., Zotenko, E. (2011). Inferring Physical Protein Contacts from Large-Scale Purification Data of Protein Complexes. Molecular and Cellular Proteomics, 10(6), 1-15. [More Information]
  • Canzar, S., Elbassioni, K., Klau, G., Mestre, J. (2011). On Tree-Constrained Matchings and Generalizations. 38th International Colloquium on Automata, Languages and Programming, ICALP 2011, Heidelberg, Germany: Springer. [More Information]
  • Khuller, S., Malekian, A., Mestre, J. (2011). To Fill or Not to Fill: The Gas Station Problem. ACM Transactions on Algorithms, 7(3), 36:1-36:16. [More Information]

2010

  • Canzar, S., Elbassioni, K., Mestre, J. (2010). A Polynomial Delay Algorithm for Enumerating Approximate Solutions to the Interval Constrained Coloring Problem. 12th Workshop on Algorithm Engineering and Experiments 2010 (ALENEX10), United States of America: Society for Industrial and Applied Mathematics (SIAM).
  • Bar-Yehuda, R., Flysher, G., Mestre, J., Rawitz, D. (2010). Approximation of Partial Capacitated Vertex Cover. SIAM Journal on Discrete Mathematics, 24(4), 1441-1469. [More Information]
  • Garg, N., Kavitha, T., Kumar, A., Mehlhorn, K., Mestre, J. (2010). Assigning Papers to Referees. Algorithmica: an international journal in computer science, 58(1), 119-136. [More Information]
  • Seufert, S., Bedathur, S., Mestre, J., Weikum, G. (2010). Bonsai: Growing Interesting Small Trees. 10th IEEE International Conference on Data Mining (ICDM 2010), USA: (IEEE) Institute of Electrical and Electronics Engineers. [More Information]
  • Epstein, L., Levin, A., Mestre, J., Segev, D. (2010). Improved Approximation Guarantees for Weighted Matching in the Semi-Streaming Model. [More Information]
  • Hajiaghayi, M., Khandekar, R., Kortsarz, G., Mestre, J. (2010). The Checkpoint Problem. 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2010), Germany: Springer.
  • Epstein, L., Levin, A., Marchetti-Spaccamela, A., Megow, N., Mestre, J., Skutella, M., Stougie, L. (2010). Universal Sequencing on a Single Machine. 14th Conference on Integer Programming and Combinatorial Optimization (IPCO XIV) 2010, Berlin: Springer.
  • Bansal, N., Gupta, A., Li, J., Mestre, J., Nagarajan, V., Rudra, A. (2010). When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings (Extended Abstract). 18th Annual European Symposium on Algorithms ESA 2010 (ALGO 2010), Berlin: Springer.

2009

  • Elbassioni, K., Krohn, E., Matijevic, D., Mestre, J., Severdija, D. (2009). Improved Approximations for Guarding 1.5-Dimensional Terrains. 26th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2009), Freiburg: IBFI Schloss Dagstuhl.
  • Kavitha, T., Mestre, J. (2009). Max-Coloring Paths: Tight Bounds and Extensions. 20th International Symposium on Algorithms and Computation ISAAC 2009, Germany: Springer.
  • Epstein, L., Kleiman, E., Mestre, J. (2009). Parametric Packing of Selfish Items and the Subset Sum Algorithm. Lecture Notes in Computer Science (LNCS), 5929, 67-78.
  • Kavitha, T., Mestre, J., Nasre, M. (2009). Popular Mixed Matchings. 36th International Colloquium on Automata, Languages and Programming (ICALP 2009), Germany: Springer.

2008

  • Mestre, J. (2008). Adaptive Local Ratio. 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008), Philadelphia: Society for Industrial and Applied Mathematics (SIAM).
  • Khuller, S., Mestre, J. (2008). An Optimal Incremental Algorithm for Minimizing Lateness with Rejection. 16th Annual European Symposium on Algorithms ESA 2008, Germany: Springer.
  • Althaus, E., Canzar, S., Elbassioni, K., Karrenbauer, A., Mestre, J. (2008). Approximating the Interval Constrained Coloring Problem. Lecture Notes in Computer Science (LNCS), 5124, 210-221. [More Information]
  • Mestre, J. (2008). Lagrangian Relaxation and Partial Cover. 25th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2008), Leibniz: IBFI Schloss Dagstuhl.
  • Zotenko, E., Mestre, J., O'Leary, D., Przytycka, T. (2008). Why Do Hubs in the Yeast Protein Interaction Network Tend To Be Essential: Reexamining the Connection between the Network Topology and Essentiality. PLoS Computational Biology, 4(8), e1000140-1-e1000140-16. [More Information]

2007

  • Bar-Yehuda, R., Flysher, G., Mestre, J., Rawitz, D. (2007). Approximation of Partial Capacitated Vertex Cover. 15th Annual European Symposium on Algorithms ESA 2007, Germany: Springer.
  • Khuller, S., Malekian, A., Mestre, J. (2007). To Fill or Not to Fill: The Gas Station Problem. 15th Annual European Symposium on Algorithms ESA 2007, Germany: Springer.

2006

  • Gandhi, R., Mestre, J. (2006). Combinatorial Algorithms for Data Migration to Minimize Average Completion Time. 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2006), Germany: Springer.
  • Mestre, J. (2006). Greedy in Approximation Algorithms. 14th Annual European Symposium on Algorithms ESA 2006, Germany: Springer.
  • Mestre, J. (2006). On the multi-radius cover problem. Information Processing Letters, 99(6), 195-198. [More Information]
  • Mestre, J. (2006). Weighted Popular Matchings. 33rd International Colloquium on Automata, Languages and Programming (ICALP 2006), Germany: Springer.

2005

  • Mestre, J. (2005). A Primal-Dual Approximation Algorithm for Partial Vertex Cover: Making Educated Guesses. 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2005), Germany: Springer.

For support on your academic profile contact .