Dr Julian Mestre

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

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]
  • 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]
  • Aziz, H., Mestre, J. (2014). Parametrized algorithms for random serial dictatorship. Mathematical Social Sciences, 72, 1-6. [More Information]
  • Mestre, J. (2014). Weighted popular matchings. ACM Transactions on Algorithms, 10(1), 1-16. [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.
  • 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]
  • 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]
  • Aziz, H., Mestre, J. (2014). Parametrized algorithms for random serial dictatorship. Mathematical Social Sciences, 72, 1-6. [More Information]
  • Mestre, J. (2014). Weighted popular matchings. ACM Transactions on Algorithms, 10(1), 1-16. [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.

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 .