Monaldo Mastrolilli

On the generation of Metric TSP instances with a large integrality gap by branch-and-cut.

  • Luca Maria Gambardella
  • Stefano Gualandi
  • Monaldo Mastrolilli
  • Eleonora Vercesi
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization Tags , , ,

    This paper introduces a computational method for generating metric Travelling Salesperson Problem (TSP) instances having a large integrality gap. The method is based on the solution of an NP-hard problem, called IH-OPT, that takes in input a fractional solution of the Subtour Elimination Problem (SEP) on a TSP instance and compute a TSP instance having … Read more

    Minimizing the sum of weighted completion times in a concurrent open shop

  • Monaldo Mastrolilli
  • Maurice Queyranne
  • Andreas S. Schulz
  • Nelson A. Uhan
  • Ola Svensson
    • Categories (Mixed) Integer Linear Programming, Approximation Algorithms, Scheduling Tags , , ,

    We study minimizing the sum of weighted completion times in a concurrent open shop. We give a primal-dual 2-approximation algorithm for this problem. We also show that several natural linear programming relaxations for this problem have an integrality gap of 2. Finally, we show that this problem is inapproximable within a factor strictly less than … Read more