7 papers
Inclusion-wise extremal knapsack problems are (mostly) hard to approximate
Fabio Ciccarelli, Fabio Furini, Ulrich Pferschy +1
We study two inclusion-wise extremal variants of the 0-1 Knapsack Problem (KP). Given items with integer weights and nonnegative costs or profits, the Minimum-Cost Maximal Knap…
A tight 1/3-approximation algorithm and fully polynomial-time approximation schemes for the Colored Knapsack Problem
Fabio Ciccarelli, Fabio Furini
The (ColKP) generalizes the classical Knapsack Problem by partitioning the items into color classes and requiring the selected items to admit an…
The colored knapsack problem: structural properties and exact algorithms
Fabio Ciccarelli, Alexander Helber, Erik Mühmer
We introduce and study a novel generalization of the classical Knapsack Problem (KP), called the Colored Knapsack Problem (CKP). In this problem, the items are partitioned into cla…
Branch-and-price strikes back for the k-vertex cut problem
Fabio Ciccarelli, Fabio Furini, Christopher Hojny +1
Given an undirected graph, the k-vertex cut problem (k-VCP) asks for a minimum-cost set of vertices whose removal yields at least k connected components in the resulting graph. The…
A Tight 2-Approximation Algorithm for the Bin Packing Problem with Setups
Roberto Baldacci, Fabio Ciccarelli, Stefano Coniglio +2
We study approximation algorithms for the Bin Packing Problem with Setups (BPPS), a generalization of the classical Bin Packing Problem (BPP) in which items are partitioned into cl…
The Bin Packing Problem with Setups: Formulations, Structural Properties and Computational Insights
Roberto Baldacci, Fabio Ciccarelli, Stefano Coniglio +2
We introduce the Bin Packing Problem with Setups (BPPS), a generalization of the classical Bin Packing Problem with applications in production planning and logistics. In this probl…
Strength of the Upper Bounds for the Edge-Weighted Maximum Clique Problem
Fabio Ciccarelli, Valerio Dose, Fabio Furini +1
We theoretically and computationally compare the strength of the three main upper bounds from the literature on the optimal value of the Edge-Weighted Maximum Clique Problem (EWMCP…