This special issue of the Journal of Combinatorial Optimization is devoted to ECCO XXXII, the annual conference of the European Chapter on Combinatorial Optimization (ECCO). The conference took place in St. Julian’s, Malta, between Thursday 30 May and Saturday 1 June 2019.

ECCO XXXII was an international event with about 90 participants from 25 different countries coming from over 50 different universities. The scientific program included 62 contributed talks on a broad range of subjects within combinatorial optimization. The subjects included exact and approximation algorithms, integer programming, scheduling, heuristics, meta-heuristics, topics in graph and hypergraph theory including domination, colourings and spectral theory, and applications of combinatorial optimization in areas such as bio-informatics, logistics, supply chain management, routing, energy production, manufacturing and tomography, amongst others.

Four plenary lectures were delivered by:

  • Fred Glover (University of Colorado Boulder, United States) and Gary A. Kochenberger (University of Colorado Denver, United States) on QUBO Models in Optimization, Machine Learning, and Quantum Computing;

  • Martin Charles Golumbic (University of Haifa, Israel) on The Wonderful World of Chordal Graphs;

  • Alexander S. Kulikov (St. Petersburg Department of Steklov Institute of Mathematics, Russia) on Boolean Circuit Size: Overview of known results and open problems;

  • Maria Grazia Speranza (Università degli Studi di Brescia, Italy) on Integrated and collaborative routing problems.

The Scientific and the Organizing Committees of ECCO XXXII were both chaired by John Baptist Gauci from the University of Malta. The conference program was designed to offer a blend of experiences to the participants, focusing on providing an opportunity for a healthy exchange of scientific ideas, but featuring also the social and leisure dimensions whilst getting a taste of what Malta has to offer. Malta is an island state in the middle of the Mediterranean Sea. The three inhabited islands cover 316 km\(^2\) and are home to a population of approximately 515,000 people. The Maltese islands are dotted with countless archeological and architectural gems, including seven megalithic temples which are some of the oldest free-standing structures in the world. Malta’s location on the crossroads between Europe, North Africa and the Middle East shaped its identity, history, culture, heritage and language.

A welcome reception was held on Thursday evening in the terrace of the Conference location, the Cavalieri Art Hotel. The conference excursion was held on Friday afternoon. The participants had the opportunity to visit the megalithic temple complex of Haġar Qim dating back to approximately 3600 BC, the complex of St. Paul’s Catacombs in Rabat that represents the earliest archeological evidence of Christianity in Malta, and the old capital city Mdina. The conference dinner was a barbecue that took place in the private lido of the Cavalieri Art Hotel by the main pool surrounded by the Mediterranean Sea. More information (including pictures) can be found on https://ecco2019.euro-online.org/. An article about combinatorial optimization and ECCO XXXII was published by The Sunday Times of Malta on 16 June 2019 and can be found on https://timesofmalta.com/articles/view/combinatorial-optimisation-and-a-conference-in-malta.714028.

figure a

The ECCO conferences are held on a regular basis (once a year, in Spring) and are devoted to all aspects of combinatorial optimization. They are usually attended by around 100 participants and nicely combine scientific works and the exchange of new ideas within an exciting atmosphere. Since 2006, every fourth year, the ECCO annual conference is jointly organized with CO. The latest ECCO (and ECCO-CO) conferences (2000–) were held in Capri, Bonn, Lugano, Molde, Beirut, Minsk, Porto, Cyprus, Dubrovnik, Jerusalem, Malaga, Amsterdam, Antalya, Paris, Munich, Catania, Budapest, Koper, Fribourg and Malta. In the same period, seventeen special issues dedicated to the ECCO conferences have appeared: eight in the European Journal of Operational Research (Burkard et al. 2000; Gambardella and Martello 2005; Hasle et al. 2006; Improta and Martello 2002; Kovalyov and Martello 2008; Krarup and Pisinger 2000; Martello and Pesch 2005; Maurras and Martello 2002), one in each of Computational Optimization and ApplicationsMartello and Vladimirou (2011), Journal of Scheduling Błażewicz et al. (2011), Annals of Operations Research Escudero et al. (2013), OptimizationMartello et al. (2013), and five on Discrete Applied Mathematics (Brodnik and Martello 2019; Chen et al. 2017, 2021; Jordán et al. 2018; Ries and Martello 2015).

The ECCO XXXIII conference, scheduled for St. Petersburg, Russia, in June 2020, was canceled due to the COVID-19 emergency. The ECCO XXXIV conference, scheduled for Madrid, was held online on June 10–11, 2021. The next meeting, ECCO XXXV - CO 2022 Joint Conference will be held (hopefully on site) on June 9–11, 2022, in St. Petersburg (Russia), see https://ecco2022.euro-online.org/.

The present issue of the Journal of Combinatorial Optimization is devoted to the presentation of a selection of papers presented at the conference (or submitted later by ECCO members). Twelve manuscripts were submitted. After a thorough refereeing process, six papers have been accepted for publication. Their brief descriptions are given below.

Johannes Blum, Stefan Funke, and Sabine Storandt study the complexity of commonly used practical techniques for computing shortest paths in road or grid networks with bounded growth. The three most commonly used methods for answering such shortest path queries are contraction hierarchies, hub labels and transit nodes. In their work, the authors use the very intuitive notion of bounded growth graphs to show that this suffices to prove sublinear search spaces for the three above-mentioned shortest path planning techniques. Furthermore, they argue that their preprocessing methods are close to the ones used in practice and only require expected polynomial time, hence providing a possible indication of why these algorithms perform so fast in practice.

Baruch Mor and Gur Mosheiov consider extensions of the classical single machine common due-date (CON) and common due-window (CONW) assignment problems to the setting of lot scheduling. In lot scheduling, a number of customer orders of different sizes may be processed in the same lot and order splitting between consecutive lots is allowed. The objective is to find the order allocation to lots, such that the total cost of earliness, tardiness and due-date/due-window is minimized. The authors introduce, under realistic assumptions, polynomial-time dynamic programming algorithms for both extensions. Numerical tests indicate that both algorithms can easily solve medium-size problems.

A Hamiltonian decomposition problem of partitioning a regular graph into edge-disjoint Hamiltonian cycles is considered by Andrei Nikolaev and Anna Kozlova. They present a new method for verifying vertex adjacency in the 1-skeleton of the traveling salesperson polytope based on finding a vertex-disjoint cycle cover of a related 4-regular multigraph using a heuristic general variable neighborhood search algorithm. Their algorithm was tested on random directed and undirected Hamiltonian cycles and on pyramidal tours.

Irene Sciriha, Xandru Mifsud, and James Borg consider nullspace vertex partition in graphs. The core vertex set of a graph consists of those vertices associated with the non-zero entries of the nullspace vectors of an adjacency matrix. The remaining vertices of the graph form the core-forbidden vertex set. For graphs with independent core vertices, the nullspace induces a well defined three part vertex partition: the core vertex set, their neighbors and the remote core-forbidden vertices (not adjacent to any core vertex). The authors show, among other properties, that this set can be removed, leaving the nullity unchanged.

Jing Wang, Liying Kang, and Erfang Shan consider the maximum modulus of the eigenvalues of the adjacency tensor \(\mathcal {A}(H)\) of a connected hypergraph H, called the spectral radius of H. For a non-negative parameter \(\alpha \) which is less than 1, the \(\alpha \)-spectral radius of H is given by the maximum modulus of the eigenvalues of the hypermatrix \(\alpha \mathcal {D}(H) +(1-\alpha )\mathcal {A}(H)\), where \(\mathcal {D}(H)\) is the diagonal tensor of degrees of H. The authors provide some bounds on the positive unit eigenvector corresponding to the \(\alpha \)-spectral radius of connected uniform hypergraphs and of connected general hypergraphs.

Yakov Zinder, Alexandr Kononov, and Joey Fung study a two-machine scheduling problem where each job must be processed on a first-stage machine and then on second-stage machine. In order to be processed, each job requires storage space whose availability is limited and whose consumption varies from job to job. The goal is to minimize the time needed for the completion of all jobs. The authors classify all instances of the considered scheduling problem by means of five parameters. This leads to the sixty four families of instances. For each family, they establish its computational complexity and, in the case of polynomial-time solvability, present a polynomial-time algorithm.