Journal Publications

On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy. (Coauthors: Adam Kurpisz, Samuli Leppanen), to appear in Mathematics of Operations Research.}
Bi-criteria and approximation algorithms for restricted matchings. (Coauthor: Georgios Stamoulis) Theoretical Computer Science 540: 115-132 (2014).
The Feedback Arc Set Problem with Triangle Inequality is a Vertex Cover Problem, Algorithmica 70(2): 326-339 (2014), Springer. (Invited paper to the special issue of Algorithmica devoted to the best papers of LATIN 12.)
On the approximation of minimum cost homomorphism to bipartite graphs. (Coauthor: A. Rafiey), Discrete Applied Mathematics, vol. 161(4-5): 670-676, 2013.}
Single Machine Scheduling with Scenarios. (Coauthors: N. Mutsanas, and O. Svensson), Theoretical Computer Science, vol. 477: 57-66 (2013) 2013.}
Vertex Cover in Graphs with Locally Few Colors (Coauthor: F. Kuhn), Information and Computation, 222: 265-277, 2013 (invited paper, special issue dedicated to the best papers of ICALP 2011), 2012.
Hardness of Approximating Flow and Job Shop Scheduling Problems (Coauthor: O. Svensson), Journal of the ACM 58(5): 20, 2011.
On the Approximability of Single Machine Scheduling with Precedence Constraints (Coauthors: C. Ambuehl, N. Mutsanas, and O. Svensson), Mathematics of Operations Research, November 2011, vol. 36, no. 4, 653-669 .
Inapproximability results for Maximum Edge Biclique, Optimal Linear Arrangement and Sparsest Cut (Coauthors: C. Ambuehl and O. Svensson), in SIAM Journal on Computing, 40(2): 567-596, 2011.
Minimizing the sum of weighted completion times in a concurrent open shop (Coauthors: M. Queyranne, A. S. Schulz, O. Svensson, N. A. Uhan), Operations Research Letters 38(5): 390-395, 2010.
On the Use of Different Types of Knowledge in Metaheuristics Based on Constructing Solutions (Coauthor: C. Blum), in Engineering Applications of Artificial Intelligence, Volume 23 , Issue 5, pp. 650-659, 2010.
Single machine precedence constrained scheduling is a vertex cover problem (Coauthor: C. Ambuehl), Algorithmica 53(4), pp. 488-503, (invited paper, special issue dedicated to the best papers of the European Symposium of Algorithms '06), 2009.
Precedence Constraint Scheduling and Connections to Dimension Theory of Partial Orders. (Coauthors: Christoph Ambuehl, Nikos Mutsanas and Ola Svensson.) Invited Survey in the Algorithmics Column by Gerhard J. Woeginger of the Bulletin of the European Association for Theoretical Computer Science (EATCS) , number 95, pp. 37-58, 2008.
Hybridizations of Metaheuristics With Branch and Bound Derivates (Coauthors: C. Blum, C. Cotta, A. J. Fernandez, J. E. Gallardo), in Hybrid Metaheuristics: An Emerging Approach to Optimization, Book Series: Studies in Computational Intelligence, Volume 114/2008, pp. 85-116, Springer Berlin, 2008.
A. Fishkin, K. Jansen, and M. Mastrolilli. Grouping techniques for scheduling problems: simpler and faster. Algorithmica, 51(2):183-199, 2008. [ bib | .pdf ]
R. Montemanni, J. Barta, M. Mastrolilli, and L.M. Gambardella. The robust traveling salesman problem with interval data. Transportation Science, 41(3):366-381, 2007. [ bib ]
M. Mastrolilli. A linear time approximation schemes for the single machine scheduling problem with controllable processing times. Journal of Algorithms, 59:37-52, 2006.[ bib | .pdf ]
M. Mastrolilli and M. Hutter. Hybrid rounding techniques for knapsack problems. Discrete Applied Mathematics, 154:640-649, 2006.[ bib | .pdf ]
C. Ambühl and M. Mastrolilli. Scheduling to minimize max flow time: An optimal preemptive algorithm. Operations Research Letters, 33(6):597-602, 2005. [ bib | .pdf ]
L. Bianchi, M. Birattari, M. Manfrin, M. Mastrolilli, L. Paquete, O. Rossi-Doria, and T. Schiavinotto. Hybrid metaheuristics for the vehicle routing problem with stochastic demands. Journal of Mathematical Modelling and Algorithms, 5(1):91-110, 2006. [ bib | .pdf ]
K. Jansen, M. Mastrolilli, and R. Solis-Oba. Approximation algorithms for flexible job shop problems. International Journal of Foundations of Computer Science, 16(2):361-379, 2005. [ bib | .pdf ]
K. Jansen, M. Mastrolilli, and R. Solis-Oba. Approximation schemes for job shop scheduling problems with controllable processing times. European Journal of Operational Research, 167(2):297-319, 2005. [ bib | .pdf ]
M. Mastrolilli and L. M. Gambardella. Maximum satisfiability: How good are tabu search and plateau moves in the worst-case? European Journal of Operational Research, 166(1):63-76, 2005. [ bib | .pdf ]
M. Mastrolilli and L. Bianchi. Core instances for testing: a case study. European Journal of Operational Research, 166(1):51-62, 2005. [ bib | .pdf ]
M. Mastrolilli. Scheduling to minimize max flow time: Off-line and on-line algorithms. International Journal of Foundations of Computer Science, 15:385-401, 2004. [ bib | .pdf ]
K. Jansen and M. Mastrolilli. Approximation schemes for parallel machine scheduling problems with controllable processing times. Computers and Operations Research, 31:1565-1581, 2004. [ bib | .pdf ]
M. Mastrolilli. Notes on max flow time minimization with controllable processing times. Computing, 71:375-386, 2003. [ bib | .pdf ]
M. Mastrolilli. Efficient approximation schemes for scheduling problems with release dates and delivery times. Journal of Scheduling, 6:521-531, 2003. [ bib | .pdf ]
L.M. Gambardella, M. Mastrolilli, A. Rizzoli, and M. Zaffalon. Managing resource allocation, scheduling and simulation for an intermodal container terminal. Journal of the Belgian Operations Research Society, 40:195-209, 2002. [ bib ]
L.M. Gambardella, M. Mastrolilli, A. Rizzoli, and M. Zaffalon. An optimization methodology for intermodal terminal management. Journal of Intelligent Manufacturing, 12:521-534, 2001. [ bib | .pdf ]
M. Mastrolilli and L. M. Gambardella. Effective neighbourhood functions for the flexible job shop problem. Journal of Scheduling, 3:3-20, 2000. [ bib | .html | .pdf ]

Conference Publications

Tight Sum-of-Squares lower bounds for binary polynomial optimization problems, ICALP 2016 (track A).
Sum-of-Squares lower rank upper bounds for matching problems, ISCO 2016
Sum-Of-Squares hierarchy lower bounds for symmetric formulations, IPCO 2016
Semidefinite and linear programming integrality gaps for scheduling identical machines, IPCO 2016
On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy. ICALP (1) 2015
(to appear in Mathematics of Operations Research 2016)
A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem. ESA 2015
How to sell hyperedges: the hyper matching assignment problem SODA 2013

Approximation of Minimum Cost Homomorphisms. (Coauthors: P. Hell, M. Nevisi and A. Rafiey), in Proceedings of the 20th Annual European Symposium on Algorithms (ESA), 2012.
Competitive Ratio Approximation Schemes for Makespan Scheduling Problems. (Coauthors: A. Kurpisz, G. Stamoulis), in Proceedings of the 10th Workshop on Approximation and Online Algorithms, WAOA 2012.
Restricted Max-Min Fair Allocations with Inclusion-free Intervals. (Coauthor: G. Stamoulis), Proceedings of COCOON 2012.
The Feedback Arc Set Problem with Triangle Inequality is a Vertex Cover Problem, Proceedings of LATIN'12, Latin American Symposium on Theoretical Informatics, 2012.
Constrained Matching Problems in Bipartite Graphs (Coauthor: G. Stamoulis), Proceedings of the International Symposium on Combinatorial Optimization, ISCO 2012.
Vertex Cover in Graphs with Locally Few Colors (Coauthor: F. Kuhn), Proceedings of ICALP (1) 2011, pp. 498-509. Invited to the Special issue of Information and Computation.
Improved Bounds for Flow Shop Scheduling (Coauthor: O. Svensson), Proceedings of ICALP (1) 2009, pp. 677-688.
Mastrolilli and O. Svensson, (Acyclic) Job Shops are Hard to Approximate, Proceedings of the 49th AnnualI EEE Symposium on Foundations of ComputerScience (FOCS), pp. 583-592, 2008. [Full version]
M. Mastrolilli, N. Mutsanas and O. Svensson, Approximating Single Machine Scheduling with Scenarios. In: Ashish Goel, editor, 11th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems - APPROX 2008, LNCS 5171, pp. 153-164. Springer-Verlag, 2008.
Christoph Ambühl, Monaldo Mastrolilli, and Ola Svensson. Inapproximability results for sparsest cut, optimal linear arrangement, and precedence constraint scheduling. In Proceedings of FOCS 2007, 2007. [ bib | .html | .ps ]
Christoph Ambühl, Monaldo Mastrolilli, Nikos Mutsanas, and Ola Svensson. Scheduling with precedence constraints of low fractional dimension. In Proceedings of IPCO 2007, volume LNCS 4168, pages 28-39. Springer, 2007. [ bib | .pdf ]
Christoph Ambühl, Monaldo Mastrolilli, and Ola Svensson. Approximating precedence-constrained single machine scheduling by coloring. In Proceedings of the APPROX + RANDOM, volume LNCS 4110, pages 15-26. Springer, 2006. [ bib ]
Christoph Ambühl and Monaldo Mastrolilli. Single machine precedence constrained scheduling is a vertex cover problem. In Proceedings of the 14th Annual European Symposium on Algorithms (ESA), volume 4168 of 28-39. Springer, 2006. [ bib ]
Monaldo Mastrolilli and Luca Maria Gambardella. Max-2-sat: How good is tabu search in the worst-case? In AAAI, pages 173-178, 2004. [ bib | .pdf ]
A. Fishkin, K. Jansen, and M. Mastrolilli. On minimizing average weighted completion time: A ptas for the job shop problem with release dates. In In Proceedings of the 14th Annual International Symposium on Algorithms and Computation (ISAAC 2003), volume LNCS 2906, pages 319-328. Springer, 2003. [ bib ]
M. Mastrolilli. Scheduling to minimize max flow time: Off-line and on-line algorithms. In In Proceedings of the 14th International Symposium on Fundamentals of Computation Theory (FCT 2003), volume LNCS 2751, pages 49-60. Springer, 2003. [ bib ]
M. Mastrolilli and L. Bianchi. Core instances for testing: a case study (extended abstract). In In Proceedings of the 2nd International Workshop on Experimental and Efficient Algorithms (WEA'03), volume LNCS 2647, pages 209-221. Springer, 2003. [ bib ]
Olivia Rossi-Doria, Michael Sampels, Mauro Birattari, Marco Chiarandini, Marco Dorigo, Luca Maria Gambardella, Joshua D. Knowles, Max Manfrin, Monaldo Mastrolilli, Ben Paechter, Luis Paquete, and Thomas Stützle. A comparison of the performance of different metaheuristics on the timetabling problem. In Practice and Theory of AutomatedTimetabling IV, volume LNCS 2740, pages 329-351, 2003. [ bib ]
M. Mastrolilli. A PTAS for the single machine scheduling problem with controllable processing times. In Algorithm Theory - Proceedings of the 8th Scandinavian Workshop on Algorithm Theory (SWAT'02), volume LNCS 2368, pages 51-59. Springer, 2002. [ bib ]
Michael Sampels, Christian Blum, Monaldo Mastrolilli, and Olivia Rossi-Doria. Metaheuristics for group shop scheduling. In PPSN, pages 631-640, 2002. [ bib ]
A. Fishkin, K. Jansen, and M. Mastrolilli. Grouping techniques for scheduling problems: simpler and faster. In 9th Annual European Symposium on Algorithms (ESA'01), volume LNCS 2161, pages 206-217. Springer, 2001. [ bib | .ps ]
M. Mastrolilli. Combining arithmetic and geometric rounding techniques for knapsack problems. In Proceedings of 1st International Workshop on Efficient Algorithms (WEA'01), volume LNCS 2138, pages 525-534. Springer, 2001. [ bib ]
K. Jansen, M. Mastrolilli, and R. Solis-Oba. Job shop scheduling problems with controllable processing times. In Proceedings of the 7th Italian Conference on Theoretical Computer Science (ICTCS'01), volume LNCS 2202, pages 107-122. Springer, 2001. [ bib ]
M. Mastrolilli. Grouping techniques for one machine scheduling subject to precedence constraints. In Proceedings of the 21st Foundations of Software Technology and Theoretical Computer Science (FSTTCS'01), volume LNCS 2245, pages 268-279. Springer, 2001. [ bib ]
K. Jansen and M. Mastrolilli. Parallel machine scheduling problems with controllable processing times. In Proceedings of ICALP Workshops 2000 (ARACNE'00), pages 179-189, 2000. [ bib ]
K. Jansen, M. Mastrolilli, and R. Solis-Oba. Approximation algorithms for flexible job shop problems. In In Proceedings of Latin American Theoretical Informatics 2000, volume LNCS 1776, pages 68-77, 2000. [ bib ]
M. Zaffalon, A. Rizzoli, M. Mastrolilli, and L.M. Gambardella. Simulation for the evaluation of optimised operations policies in a container terminal. In Proceedings of the international workshop on Harbour, Maritime & Logistics Modelling and Simulation, 1999. [ bib ]
N. Fornara, L.M. Gambardella, M. Mastrolilli, A. Rizzoli, and M. Zaffalon. Simulation for policy evaluation, planning and decision support in an intermodal container terminal. In Proceedings of the International Workshop Modeling and Simulation within a Maritime Environment, pages 33-38, 1998. [ bib ]
M. Mastrolilli, M. Zaffalon, A. Rizzoli, and L.M. Gambardella. Resource allocation and scheduling of operations in an intermodal terminal, in ess 98 - simulation in industry. In Proceedings of the 10TH EUROPEAN SIMULATION SYMPOSIUM AND EXHIBITION, 1998. [ bib ]

Surveys

Precedence Constraint Scheduling and Connections to Dimension Theory of Partial Orders. Joint work with C. Ambuehl, N. Mutsanas and O. Svensson. In the Algorithmics Column by Gerhard J. Woeginger of the Bulletin of the European Association for Theoretical Computer Science (EATCS) , number 95. Appeared online at http://www.eatcs.org/bulletin/beatcs95.pdf.

Book Chapters

Hybridizations of Metaheuristics With Branch and Bound Derivates (Coauthors: C. Blum, C. Cotta, A. J. Fernandez, J. E. Gallardo), in Hybrid Metaheuristics: An Emerging Approach to Optimization, Book Series: Studies in Computational Intelligence, Volume 114/2008, pp. 85-116, Springer Berlin, 2008.

Theses

M. Mastrolilli, Approximation Schemes for Scheduling Problems, PhD thesis, University of Kiel, 2002.
M. Mastrolilli, Il problema del flexible job shop: un'euristica efficiente basata sulla ricerca locale, M.Sc. thesis, Politecnico di Milano, 1997.

Edited Books

K. Jansen, M. Margraf, M. Mastrolilli, and J.D.P. Rolim, editors. Experimental and Efficient Algorithms: Second International Workshop WEA 2003, volume LCNS 2647. Springer, 2003. [ bib ]

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

Monaldo Mastrolilli