Giuseppe Lancia
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Giuseppe Lancia has a total of 56 co-authors. Here are the top co-authors by number of shared publications:
Paolo Serafini
University of Udine
17 shared publications- Paolo Serafini
University of Udine
10 shared publications - Marcello Dalpasso
DEI - University of Padova
8 shared publications - Romeo Rizzi
Department of Computer Science, University of Verona, Verona, Italy
7 shared publications Sorin Istrail
5 shared publications- Vineet Bafna
University of California San Diego
5 shared publications
Latest Publications
- Open Access
- 4 September 2025
- Published by MDPI AG in Algorithms
- Vol. 18 (9) , 560
Speeding Up Floyd–Warshall’s Algorithm to Compute All-Pairs Shortest Paths and the Transitive Closure of a Graph
Floyd–Warshall’s algorithm is a widely-known procedure for computing all-pairs shortest paths in a graph of n vertices in time complexity. A simplified version of the same algorithm computes the transitive closure of the graph with the same time complexity. The algorithm operates on an matrix, performing n inspections and no more than n updates of each matrix cell, until the final matrix is computed. In this paper, we apply a technique called SmartForce, originally devised as a performance enhancement for solving the traveling salesman problem, to avoid the inspection and checking of cells that do not need to be updated, thus reducing the overall computation time when the number, u, of cell updates is substantially smaller than . When the ratio is not small enough, the performance of the proposed procedure might be worse than that of the Floyd–Warshall algorithm. To speed up the algorithm independently of the input instance type, we introduce an effective hybrid approach. Finally, a similar procedure, which exploits suitable fast data structures, can be used to achieve a speedup over the Floyd–Warshall simplified algorithm that computes the transitive closure of a graph.- 4 September 2025
- Published by MDPI AG in Algorithms
- Vol. 18 (9) , 560
Open AccessSpeeding Up Floyd–Warshall’s Algorithm to Compute All-Pairs Shortest Paths and the Transitive Closure of a Graph
Floyd–Warshall’s algorithm is a widely-known procedure for computing all-pairs shortest paths in a graph of n vertices in time complexity. A simplified version of the same algorithm computes the transitive closure of the graph with the same time complexity. The algorithm operates on an matrix, performing n inspections and no more than n updates of each matrix cell, until the final matrix is computed. In this paper, we apply a technique called SmartForce, originally devised as a performance enhancement for solving the traveling salesman problem, to avoid the inspection and checking of cells that do not need to be updated, thus reducing the overall computation time when the number, u, of cell updates is substantially smaller than . When the ratio is not small enough, the performance of the proposed procedure might be worse than that of the Floyd–Warshall algorithm. To speed up the algorithm independently of the input instance type, we introduce an effective hybrid approach. Finally, a similar procedure, which exploits suitable fast data structures, can be used to achieve a speedup over the Floyd–Warshall simplified algorithm that computes the transitive closure of a graph. - 11 November 2024
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
Code and Data Repository for Average Case Subquadratic Exact and Heuristic Procedures for the Traveling Salesman 2-OPT Neighborhood
The repository contains all files necessary to replicate computational experiments as those reported in the paper "Average case sub-quadratic exact and heuristic procedures for the traveling salesman 2-OPT neighborhood", by Giuseppe Lancia and Paolo Vidoni, INFORMS Journal on Computing, 2024.
- 11 November 2024
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
Code and Data Repository for Average Case Subquadratic Exact and Heuristic Procedures for the Traveling Salesman 2-OPT Neighborhood
The repository contains all files necessary to replicate computational experiments as those reported in the paper "Average case sub-quadratic exact and heuristic procedures for the traveling salesman 2-OPT neighborhood", by Giuseppe Lancia and Paolo Vidoni, INFORMS Journal on Computing, 2024.
- 11 November 2024
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
Average Case Subquadratic Exact and Heuristic Procedures for the Traveling Salesman 2-OPT Neighborhood
We describe an exact algorithm for finding the best 2-OPT move that, experimentally, was observed to be much faster than the standard quadratic approach for a large part of a best-improvement local search convergence starting at a random tour. To analyze its average-case complexity, we introduce a family of heuristic procedures and discuss their complexity when applied to a random tour in graphs whose edge costs are either uniform random numbers in [0, 1] or Euclidean distances between random points in the plane. We prove that, for any probability p, there is a heuristic in the family that can find the best 2-OPT move with probability at least p in average-time [ ]) for uniform instances and [ ] for Euclidean instances. The exact algorithm is then proved to be even faster in the sense that in those instances in which a heuristic finds the best move, the exact algorithm finds it in a smaller time. We give empirical evidence that a slight variant of our algorithm finds the best move in [ ] time on both types of instances, achieving the best possible performance for this particular problem. Computational experiments are reported to show the effectiveness of our algorithms, both in best-improvement and in first-improvement 2-OPT local search. History: Accepted by Andrea Lodi, Area Editor for Design and Analysis of Algorithms: Discrete. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0169 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0169 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .
- 11 November 2024
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
Average Case Subquadratic Exact and Heuristic Procedures for the Traveling Salesman 2-OPT Neighborhood
We describe an exact algorithm for finding the best 2-OPT move that, experimentally, was observed to be much faster than the standard quadratic approach for a large part of a best-improvement local search convergence starting at a random tour. To analyze its average-case complexity, we introduce a family of heuristic procedures and discuss their complexity when applied to a random tour in graphs whose edge costs are either uniform random numbers in [0, 1] or Euclidean distances between random points in the plane. We prove that, for any probability p, there is a heuristic in the family that can find the best 2-OPT move with probability at least p in average-time [ ]) for uniform instances and [ ] for Euclidean instances. The exact algorithm is then proved to be even faster in the sense that in those instances in which a heuristic finds the best move, the exact algorithm finds it in a smaller time. We give empirical evidence that a slight variant of our algorithm finds the best move in [ ] time on both types of instances, achieving the best possible performance for this particular problem. Computational experiments are reported to show the effectiveness of our algorithms, both in best-improvement and in first-improvement 2-OPT local search. History: Accepted by Andrea Lodi, Area Editor for Design and Analysis of Algorithms: Discrete. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0169 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0169 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .
- Open Access
Algorithmic strategies for finding the best TSP 2-OPT move in average sub-quadratic time
We describe an exact algorithm for finding the best 2-OPT move which, experimentally, was observed to be much faster than the standard quadratic approach. To analyze its average-case complexity, we introduce a family of heuristic procedures and discuss their complexity when applied to a random tour in graphs whose edge costs are either uniform random numbers in [0, 1] or Euclidean distances between random points in the plane. We prove that, for any probability p: (i) there is a heuristic in the family which can find the best move with probability at least p in average-time O(n^3/2) for uniform instances and O(n) for Euclidean instances; (ii) the exact algorithm take lesser time then the above heuristic on all instances on which the heuristic finds the best move. During local search, while the tour becomes less and less random, the speed of our algorithm worsens until it becomes quadratic. We then discuss how to fine tune a successful hybrid approach, made of our algorithm in the beginning followed by the usual quadratic enumeration.
Open AccessAlgorithmic strategies for finding the best TSP 2-OPT move in average sub-quadratic time
We describe an exact algorithm for finding the best 2-OPT move which, experimentally, was observed to be much faster than the standard quadratic approach. To analyze its average-case complexity, we introduce a family of heuristic procedures and discuss their complexity when applied to a random tour in graphs whose edge costs are either uniform random numbers in [0, 1] or Euclidean distances between random points in the plane. We prove that, for any probability p: (i) there is a heuristic in the family which can find the best move with probability at least p in average-time O(n^3/2) for uniform instances and O(n) for Euclidean instances; (ii) the exact algorithm take lesser time then the above heuristic on all instances on which the heuristic finds the best move. During local search, while the tour becomes less and less random, the speed of our algorithm worsens until it becomes quadratic. We then discuss how to fine tune a successful hybrid approach, made of our algorithm in the beginning followed by the usual quadratic enumeration.
- Open Access
- 21 December 2023
- Published by Springer Nature in Journal of Heuristics
- Vol. 30 (3-4) , 109-144
Algorithmic strategies for a fast exploration of the TSP $4$-OPT neighborhoodWe describe an effective algorithm for exploring the $$4$$ -OPT neighborhood for the Traveling Salesman Problem. $$4$$ -OPT moves change a tour into another by replacing four of its edges. The best move can be found by a $$\Theta (n^4)$$ algorithm by complete enumeration, but a $$\Theta (n^3)$$ dynamic programming algorithm exists in the literature. Furthermore a $$\Theta (n^2)$$ algorithm also exists for a particular subset of symmetric $$4$$ -OPT moves. In this work we describe a new procedure which behaves, on average, slightly worse than a quadratic algorithm over all moves (estimated at $$O(n^{2.5})$$ ) and like a quadratic algorithm on the symmetric moves. Computational results are reported which show the effectiveness of our strategy compared to other algorithms for finding the best $$4$$ -OPT move, and discuss the strength of the $$4$$ -OPT neighborhood compared to 2- and $$3$$ -OPT.- 21 December 2023
- Published by Springer Nature in Journal of Heuristics
- Vol. 30 (3-4) , 109-144
Open AccessAlgorithmic strategies for a fast exploration of the TSP $4$-OPT neighborhoodWe describe an effective algorithm for exploring the $$4$$ -OPT neighborhood for the Traveling Salesman Problem. $$4$$ -OPT moves change a tour into another by replacing four of its edges. The best move can be found by a $$\Theta (n^4)$$ algorithm by complete enumeration, but a $$\Theta (n^3)$$ dynamic programming algorithm exists in the literature. Furthermore a $$\Theta (n^2)$$ algorithm also exists for a particular subset of symmetric $$4$$ -OPT moves. In this work we describe a new procedure which behaves, on average, slightly worse than a quadratic algorithm over all moves (estimated at $$O(n^{2.5})$$ ) and like a quadratic algorithm on the symmetric moves. Computational results are reported which show the effectiveness of our strategy compared to other algorithms for finding the best $$4$$ -OPT move, and discuss the strength of the $$4$$ -OPT neighborhood compared to 2- and $$3$$ -OPT. - 1 May 2022
- Published by Pleiades Publishing Ltd in Journal of Applied and Industrial Mathematics
- Vol. 16 (2) , 252-266
An ILP Approach to Determine Smallest 4-Regular Non-Hamiltonian, Nontraceable, and Nonhomogeneously Traceable Graphs
In this paper we study some open questions related to the smallest order \( f({\cal C},\lnot {\cal H}) \) of a \( 4 \)-regular graph which has a connectivity property \( {\cal C} \) but does not have a hamiltonian property \( \cal H \). In particular, \( \cal C \) is either connectivity, \( 2 \)-connectivity or \( 1 \)-toughness and \( \cal H \) is hamiltonicity, homogeneous traceability or traceability. A standard theoretical approach to these questions had already been used in the literature, but in many cases did not succeed in determining the exact value of \( f() \). Here we have chosen to use Integer Linear Programming and to encode the graphs that we are looking for as the binary solutions to a suitable set of linear inequalities. This way, there would exist a graph of order \( n \) with certain properties if and only if the corresponding ILP had a feasible solution, which we have determined through a branch-and-cut procedure. By using our approach, we have been able to compute \( f({\cal C},\lnot {\cal H}) \) for all the pairs of considered properties with the exception of \( {\cal C}= \)1-toughness, \( {{\cal H}}= \)traceability. Even in this last case, we have nonetheless significantly reduced the interval \( [LB, UB] \) in which \( f({\cal C},\lnot {\cal H}) \) was known to lie. Finally, we have shown that for each \( n \geq f({\cal C},\lnot {\cal H}) \) ( \( n \geq UB \) in the last case) there exists a \( 4 \)-regular graph on \( n \) vertices which has property \( \cal C \) but not property \( \cal H \).- 1 May 2022
- Published by Pleiades Publishing Ltd in Journal of Applied and Industrial Mathematics
- Vol. 16 (2) , 252-266
An ILP Approach to Determine Smallest 4-Regular Non-Hamiltonian, Nontraceable, and Nonhomogeneously Traceable Graphs
In this paper we study some open questions related to the smallest order \( f({\cal C},\lnot {\cal H}) \) of a \( 4 \)-regular graph which has a connectivity property \( {\cal C} \) but does not have a hamiltonian property \( \cal H \). In particular, \( \cal C \) is either connectivity, \( 2 \)-connectivity or \( 1 \)-toughness and \( \cal H \) is hamiltonicity, homogeneous traceability or traceability. A standard theoretical approach to these questions had already been used in the literature, but in many cases did not succeed in determining the exact value of \( f() \). Here we have chosen to use Integer Linear Programming and to encode the graphs that we are looking for as the binary solutions to a suitable set of linear inequalities. This way, there would exist a graph of order \( n \) with certain properties if and only if the corresponding ILP had a feasible solution, which we have determined through a branch-and-cut procedure. By using our approach, we have been able to compute \( f({\cal C},\lnot {\cal H}) \) for all the pairs of considered properties with the exception of \( {\cal C}= \)1-toughness, \( {{\cal H}}= \)traceability. Even in this last case, we have nonetheless significantly reduced the interval \( [LB, UB] \) in which \( f({\cal C},\lnot {\cal H}) \) was known to lie. Finally, we have shown that for each \( n \geq f({\cal C},\lnot {\cal H}) \) ( \( n \geq UB \) in the last case) there exists a \( 4 \)-regular graph on \( n \) vertices which has property \( \cal C \) but not property \( \cal H \).- Open Access
- 9 August 2021
- Published by MDPI AG in Algorithms
- Vol. 14 (8) , 235
Computational Complexity and ILP Models for Pattern Problems in the Logical Analysis of Data
Logical Analysis of Data is a procedure aimed at identifying relevant features in data sets with both positive and negative samples. The goal is to build Boolean formulas, represented by strings over {0,1,-} called patterns, which can be used to classify new samples as positive or negative. Since a data set can be explained in alternative ways, many computational problems arise related to the choice of a particular set of patterns. In this paper we study the computational complexity of several of these pattern problems (showing that they are, in general, computationally hard) and we propose some integer programming models that appear to be effective. We describe an ILP model for finding the minimum-size set of patterns explaining a given set of samples and another one for the problem of determining whether two sets of patterns are equivalent, i.e., they explain exactly the same samples. We base our first model on a polynomial procedure that computes all patterns compatible with a given set of samples. Computational experiments substantiate the effectiveness of our models on fairly large instances. Finally, we conjecture that the existence of an effective ILP model for finding a minimum-size set of patterns equivalent to a given set of patterns is unlikely, due to the problem being NP-hard and co-NP-hard at the same time.
- 9 August 2021
- Published by MDPI AG in Algorithms
- Vol. 14 (8) , 235
Open AccessComputational Complexity and ILP Models for Pattern Problems in the Logical Analysis of Data
Logical Analysis of Data is a procedure aimed at identifying relevant features in data sets with both positive and negative samples. The goal is to build Boolean formulas, represented by strings over {0,1,-} called patterns, which can be used to classify new samples as positive or negative. Since a data set can be explained in alternative ways, many computational problems arise related to the choice of a particular set of patterns. In this paper we study the computational complexity of several of these pattern problems (showing that they are, in general, computationally hard) and we propose some integer programming models that appear to be effective. We describe an ILP model for finding the minimum-size set of patterns explaining a given set of samples and another one for the problem of determining whether two sets of patterns are equivalent, i.e., they explain exactly the same samples. We base our first model on a polynomial procedure that computes all patterns compatible with a given set of samples. Computational experiments substantiate the effectiveness of our models on fairly large instances. Finally, we conjecture that the existence of an effective ILP model for finding a minimum-size set of patterns equivalent to a given set of patterns is unlikely, due to the problem being NP-hard and co-NP-hard at the same time.
- Open Access
- 23 November 2020
- Published by MDPI AG in Algorithms
- Vol. 13 (11) , 306
Finding the Best 3-OPT Move in Subcubic Time
Given a Traveling Salesman Problem solution, the best 3-OPT move requires us to remove three edges and replace them with three new ones so as to shorten the tour as much as possible. No worst-case algorithm better than the enumeration of all triples is likely to exist for this problem, but algorithms with average case are not ruled out. In this paper we describe a strategy for 3-OPT optimization which can find the best move by looking only at a fraction of all possible moves. We extend our approach also to some other types of cubic moves, such as some special 6-OPT and 5-OPT moves. Empirical evidence shows that our algorithm runs in average subcubic time (upper bounded by ) on a wide class of random graphs as well as Traveling Salesman Problem Library (TSPLIB) instances.- 23 November 2020
- Published by MDPI AG in Algorithms
- Vol. 13 (11) , 306
Open AccessFinding the Best 3-OPT Move in Subcubic Time
Given a Traveling Salesman Problem solution, the best 3-OPT move requires us to remove three edges and replace them with three new ones so as to shorten the tour as much as possible. No worst-case algorithm better than the enumeration of all triples is likely to exist for this problem, but algorithms with average case are not ruled out. In this paper we describe a strategy for 3-OPT optimization which can find the best move by looking only at a fraction of all possible moves. We extend our approach also to some other types of cubic moves, such as some special 6-OPT and 5-OPT moves. Empirical evidence shows that our algorithm runs in average subcubic time (upper bounded by ) on a wide class of random graphs as well as Traveling Salesman Problem Library (TSPLIB) instances. - 1 October 2020
- Published by Elsevier in European Journal of Operational Research
- Vol. 286 (2) , 458-467
Finding the largest triangle in a graph in expected quadratic time
- 1 October 2020
- Published by Elsevier in European Journal of Operational Research
- Vol. 286 (2) , 458-467
Finding the largest triangle in a graph in expected quadratic time
- 29 June 2020
- Published by Springer Nature
- p. 69-84
Using Integer Programming to Search for Counterexamples: A Case Study
- 29 June 2020
- Published by Springer Nature
- p. 69-84
Using Integer Programming to Search for Counterexamples: A Case Study