You are here: University of Sydney / Engineering & IT / About us / Our people / Dr Julian Mestre 

Dr Julian Mestre

Lecturer

J12 - The School of Information Technologies
The University of Sydney

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

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

Back to Top

Selected grants

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.
Back to Top

Selected publications

Download citations: PDF RTF Endnote

Journals

  • Kavitha, T., Mestre, J. (2012). Max-coloring paths: tight bounds and extensions. Journal of Combinatorial Optimization, 24(1), 1-14.
  • Hajiaghayi, M., Khandekar, R., Kortsarz, G., Mestre, J. (2012). The checkpoint problem. Theoretical Computer Science, 452, 88-99.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.

Conferences

  • 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 (MSWiM'12), New York: Association for Computing Machinery (ACM).
  • 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.
  • 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.
  • 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.
  • Epstein, L., Levin, A., Mestre, J., Segev, D. (2010). Improved Approximation Guarantees for Weighted Matching in the Semi-Streaming Model. 27th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2010), Germany: Schloss Dagstuhl - Leibniz Center for Informatics.
  • 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, Germany: 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. 18th Annual European Symposium on Algorithms ESA 2010 (ALGO 2010), Germany: 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), Germany: 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), United States of America: 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), France: 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.

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 (MSWiM'12), New York: Association for Computing Machinery (ACM).
  • Kavitha, T., Mestre, J. (2012). Max-coloring paths: tight bounds and extensions. Journal of Combinatorial Optimization, 24(1), 1-14.
  • 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.
  • Hajiaghayi, M., Khandekar, R., Kortsarz, G., Mestre, J. (2012). The checkpoint problem. Theoretical Computer Science, 452, 88-99.
  • 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.
  • 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.

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.
  • 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.
  • 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.
  • 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.
  • 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.

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).
  • 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.
  • 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.
  • Epstein, L., Levin, A., Mestre, J., Segev, D. (2010). Improved Approximation Guarantees for Weighted Matching in the Semi-Streaming Model. 27th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2010), Germany: Schloss Dagstuhl - Leibniz Center for Informatics.
  • 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, Germany: 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. 18th Annual European Symposium on Algorithms ESA 2010 (ALGO 2010), Germany: 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), Germany: 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), United States of America: 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.
  • Mestre, J. (2008). Lagrangian Relaxation and Partial Cover. 25th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2008), France: 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.
  • 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.
Back to Top

For support on your academic profile contact Research Support.