Valerio Dose

Optimal Macroitem Sequences in the Precedence Constrained Knapsack Problem

Categories Combinatorial Optimization, Graphs and Matroids, Linear Programming Tags , , ,

The Precedence Constrained Knapsack Problem (PCKP) asks for a maximum-profit subset of items, subject to a knapsack capacity constraint and precedence constraints encoded by a directed acyclic graph. We study the structure of optimal solutions of the Linear Programming (LP) relaxation of the natural Integer Linear Programming formulation of the PCKP. We introduce the notion … Read more

A Tight 2-Approximation Algorithm for the Bin Packing Problem with Setups

Categories Approximation Algorithms, Combinatorial Optimization

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 classes and activating a class in a bin consumes a setup weight and incurs a setup cost. We show that direct adaptations of Next Fit (NF), First Fit … Read more

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

Categories Graphs and Matroids, Integer Programming Tags , ,

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). We provide a set of instances for which the ratio between any of the three upper bounds and the optimal value of the EWMCP is unbounded, showing that … Read more