Valerio Dose

A first approximation algorithm for the Bin Packing Problem with Setups

  • Fabio Ciccarelli
  • Roberto Baldacci
  • Stefano Coniglio
  • Valerio Dose
  • Fabio Furini
    • Categories Approximation Algorithms, Combinatorial Optimization

    We study constant-factor approximation algorithms for the Bin Packing Problem with Setups (BPPS). First, we show that adaptations of classical BPP heuristics can have arbitrarily poor worst-case performance on BPPS instances. Then, we propose a two-phase heuristic for the BPPS that applies an α-approximation algorithm for the BPP to the items of each class and … Read more

    Strength of the Upper Bounds for the Edge-Weighted Maximum Clique Problem

  • Fabio Ciccarelli
  • Valerio Dose
  • Fabio Furini
  • Marta Monaci
    • Categories Graphs and Matroids, Integer Programming Tags , ,

    We theoretically and computationally compare the strength of the two main upper bounds from the literature on the optimal value of the Edge-Weighted Maximum Clique Problem (EWMCP). We provide a set of instances for which the ratio between either of the two upper bounds and the optimal value of the EWMCP is unbounded. This result … Read more