Jon Lee Giovanni Rinaldi A. Ridha Mahjoub (Eds.) 6 Combinatorial 5 8 0 1 Optimization S C N L 5th International Symposium, ISCO 2018 Marrakesh, Morocco, April 11–13, 2018 Revised Selected Papers 123 Lecture Notes in Computer Science 10856 Commenced Publication in 1973 Founding and Former Series Editors: Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen Editorial Board David Hutchison Lancaster University, Lancaster, UK Takeo Kanade Carnegie Mellon University, Pittsburgh, PA, USA Josef Kittler University of Surrey, Guildford, UK Jon M. Kleinberg Cornell University, Ithaca, NY, USA Friedemann Mattern ETH Zurich, Zurich, Switzerland John C. Mitchell Stanford University, Stanford, CA, USA Moni Naor Weizmann Institute of Science, Rehovot, Israel C. Pandu Rangan Indian Institute of Technology Madras, Chennai, India Bernhard Steffen TU Dortmund University, Dortmund, Germany Demetri Terzopoulos University of California, Los Angeles, CA, USA Doug Tygar University of California, Berkeley, CA, USA Gerhard Weikum Max Planck Institute for Informatics, Saarbrücken, Germany More information about this series at http://www.springer.com/series/7407 Jon Lee Giovanni Rinaldi (cid:129) A. Ridha Mahjoub (Eds.) Combinatorial Optimization 5th International Symposium, ISCO 2018 – Marrakesh, Morocco, April 11 13, 2018 Revised Selected Papers 123 Editors Jon Lee A.RidhaMahjoub Department ofIndustrial andOperations LAMSADE, UniversitéParis-Dauphine Engineering Paris University of Michigan France AnnArbor, MI USA GiovanniRinaldi Informatica (IASI) Istituto di Analisi dei Sistemied Rome Italy ISSN 0302-9743 ISSN 1611-3349 (electronic) Lecture Notesin Computer Science ISBN 978-3-319-96150-7 ISBN978-3-319-96151-4 (eBook) https://doi.org/10.1007/978-3-319-96151-4 LibraryofCongressControlNumber:2018947875 LNCSSublibrary:SL1–TheoreticalComputerScienceandGeneralIssues ©SpringerInternationalPublishingAG,partofSpringerNature2018 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartofthe material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodologynow knownorhereafterdeveloped. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Thepublisher,theauthorsandtheeditorsaresafetoassumethattheadviceandinformationinthisbookare believedtobetrueandaccurateatthedateofpublication.Neitherthepublishernortheauthorsortheeditors give a warranty, express or implied, with respect to the material contained herein or for any errors or omissionsthatmayhavebeenmade.Thepublisherremainsneutralwithregardtojurisdictionalclaimsin publishedmapsandinstitutionalaffiliations. ThisSpringerimprintispublishedbytheregisteredcompanySpringerNatureSwitzerlandAG Theregisteredcompanyaddressis:Gewerbestrasse11,6330Cham,Switzerland Preface ThisvolumecontainstheregularpaperspresentedatISCO2018,the5thInternational SymposiumonCombinatorialOptimization,heldinMarrakesh,MoroccoduringApril 11–13, 2018. ISCO 2018 was preceded during April 9–10 by the Spring School on “AdvancedMixedIntegerProgrammingFormulationTechniques”givenbyJuanPablo VielmaandJoyeHuchette (MIT, USA). ISCOisanew biennialsymposium.Thefirst editionwasheldinHammamet,Tunisia,inMarch2010,thesecondinAthens,Greece, inApril2012,thethirdinLisbon,Portugal,inMarch2014,andthefourthinVietriSul Mare, Italy, in May 2016. The symposium aims to bring together researchers from all the communities related to combinatorial optimization, including algorithms and complexity, mathematical programming, operations research, stochastic optimization, multi-objectiveoptimization,graphs,andcombinatorics.Itisintendedtobeaforumfor presentingoriginalresearchonallaspectsofcombinatorialoptimization,rangingfrom mathematical foundations and theory of algorithms to computational studies and practical applications, and especially their intersections. Inresponsetothecallforpapers,ISCO2018received75regularsubmissions.Each submissionwasreviewedbyatleastthreeProgramCommittee(PC)memberswiththe assistanceofexternal reviewers.Thesubmissions werejudged ontheiroriginality and technical quality and the PC had to discuss in length the reviews and make tough decisions. As a result, the PC selected 35 regular papers to be presented in the sym- posiumgivinganacceptancerateof46%(69shortpaperswerealsoselectedfromboth regular and short submissions). Four eminent invited speakers, Friedrich Eisenbrand (EPFL, Lausanne, Switzerland), Marica Fampa (Federal University of Rio de Janeiro, Brazil), Bernard Gendron (University of Montreal, Canada), and Franz Rendl (University of Klagenfurt, Graz, Austria), also gave talks at the symposium. The revised versions of the accepted regular papers and extended abstracts of the invited talks are included in this volume. WewouldliketothankalltheauthorswhosubmittedtheirworktoISCO2018,and thePCmembersandexternalreviewersfortheirexcellentwork.Wewouldalsoliketo thank our invited speakers as well as the speakers of the Spring School for their exciting lectures. They all much contributed to the quality of the symposium. Finally, we would like to thank the Organizing Committee members for their dedicated work in preparing this conference, and we gratefully acknowledge our sponsoring institutions for their assistance and support. May 2018 Jon Lee A. Ridha Mahjoub Giovanni Rinaldi Organization Program Committee Co-chairs Abdellatif El Afia Mohammed V University, Rabat, Morocco Jon Lee University of Michigan, USA A. Ridha Mahjoub Paris Dauphine University, France Giovanni Rinaldi IASI, Rome, Italy Steering Committee M. Baïou CNRS, Clermont-Auvergne University, France P. Fouilhoux Pierre and Marie Curie University, Paris, France L. Gouveia University of Lisbon, Portugal N. Maculan Federal University of Rio de Janeiro, Brazil A. R. Mahjoub Paris Dauphine University, France V. Paschos Paris Dauphine University, France G. Rinaldi IASI, Rome, Italy Program Committee M. Anjos Polytechnique Montreal, Canada F. Barahona IBM, T. J. Watson, New York, USA A. Basu Johns Hopkins University, USA Y. Benadada ENSIAS, Mohammed V University, Rabat, Morocco V. Bonifaci IASI, Rome, Italy F. Bonomo University of Buenos Aires, Argentina F. Carrabs University of Salerno, Italy R. Cerulli University of Salerno, Italy K. Chandrasekaran University of Illinois, Urbana-Champaign, USA J. Correa University of Chile, Santiago, Chile F. Eisenbrand EPFL, Lausanne, Switzerland I. Elhallaoui Polytechnique Montreal, Canada A. Elhilali Alaoui Sidi Mohamed Ben Abdellah University, Fez, Morocco M. Ettaouil Sidi Mohamed Ben Abdellah University, Fez, Morocco M. Fampa Federal University of Rio de Janeiro, Brazil S. Fujishige RIMS, Kyoto University, Japan R. Fukasawa University of Waterloo, Canada T. Fukunaga JST, PRESTO, Japan B. Gendron University of Montreal, Canada C. Gentile IASI, Rome, Italy M. Gentili University of Salerno, Italy E. Gourdin Orange Labs, Paris, France VIII Organization V. Goyal Columbia University, USA A. Gupte Clemson University, USA M. Haouari University of Qatar, Qatar I. Kacem LCOMS, University of Lorraine, Metz, France V. Kaibel Otto-von-Guericke Universität, Magdeburg, Germany N. Kamiyama Kyushu University, Japan Y. Kobayashi University of Tsukuba, Japan M. Labbé Free University, Brussels, Belgium M. Lampis Paris-Dauphine University, France A. Letchford Lancaster University, UK L. Liberti LIX, Ecole Polytechnique, Paris, France I. Ljubic ESSEC, Paris, France M. Lübbecke RWTH Aachen University, Germany S. Mattia IASI, Rome, Italy S. T. McCormick UBC, Vancouver, Canada V. Nagarajan University of Michigan, USA P. Pesneau University of Bordeaux, France F. Rendl University of Klagenfurt, Graz, Austria J. J. Salazar Universidad de La Laguna, Tenerife, Spain Gonzalez A. Toriello Georgia Institute of Technology, USA P. Toth University of Bologna, Italy E. Uchoa UFF Rio de Janeiro, Brazil P. Ventura IASI, Rome, Italy S. Weltge ETHZ Zürich, Switzerland H. Yaman Bilkent University, Ankara, Turkey Organizing Committee Rdouan Faizi (Chair) Mohammed V University, Rabat, Morocco Abdellatif El Afia Mohammed V University, Rabat, Morocco Raddouane Chiheb Mohammed V University, Rabat, Morocco Sanaa El Fkihi Mohammed V University, Rabat, Morocco Pierre Fouilhoux Pierre and Marie Curie University, Paris, France Rohaifa Khaldi Mohammed V University, Rabat, Morocco A. Ridha Mahjoub Paris Dauphine University, France Sébastien Martin Lorraine University, Metz, France Fatima Ouzayd Mohammed V University, Rabat, Morocco Additional Reviewers Arbib, Claudio Bansal, Manish Arslan, Okan Bayram, Vedat Au, Gary Bazgan, Cristina Bacci, Tiziano Bentz, Cédric Organization IX Boecker, Sebastian Messaoudi, Mayssoun Bornstein, Claudson Mommessin, Clément Chakrabarty, Deeparnab Mömke, Tobias Da Fonseca, Guilherme D. Nederlof, Jesper De Souza, Cid C. Neto, Jose Deza, Antoine Oliveira Colares, Rafael El Housni, Omar Oriolo, Gianpaolo Galtier, Jerome Ouzineb, Mohamed Goerigk, Marc Paat, Joseph Gouleakis, Themis Poss, Michael Grappe, Roland Pralat, Pawel Hassani, Rachid Raiconi, Andrea Ignatius, Joshua Raupp, Fernanda Kerivin, Herve Ruthmair, Mario Khosravian Ghadikolaei, Mehdi Segev, Danny Kocuk, Burak Simonetti, Luidi Lange, Julia Souza, Uéverton Leite Bulhões Júnior, Teobaldo Stamoulis, Georgios Macambira, Ana Flavia Stecco, Gabriella Marinelli, Fabrizio Yang, Boshi Sponsoring Institutions ENSIAS, Morocco LAMSADE, Université Paris Dauphine, CNRS, France Université Mohammed V de Rabat, Morocco Plenary Lectures