Ivana Ljubić Given a set of n items with profits and weights and a knapsack capacity C, we study the problem of finding a maximal knapsack packing that minimizes the profit of selected items. We propose for the first time an effective dynamic programming (DP) algorithm which has O(nC) time complexity and O(n+C) space complexity. We demonstrate … Read more
In this work we present a branch-and-bound (B&B) framework for the asymmetric prize-collecting Steiner tree problem (APCSTP). Several well-known network design problems can be transformed to the APCSTP, including the Steiner tree problem (STP), prize-collecting Steiner tree problem (PCSTP), maximum-weight connected subgraph problem (MWCS) and the node-weighted Steiner tree problem (NWSTP). The main component of … Read more
This paper provides a study of integer linear programming formulations for the diameter constrained spanning tree problem (DMSTP) in the natural space of edge design variables. After presenting a straightforward model based on the well known jump inequalities a new stronger family of circular-jump inequalities is introduced. These inequalities are further generalized in two ways: … Read more
In this paper, the first approach for solving the vertex-biconnectivity augmentation problem (V2AUG) to optimality is proposed. Given a spanning subgraph of an edge-weighted graph, we search for the cheapest subset of edges to augment this subgraph in order to make it vertex-biconnected. The problem is reduced to the augmentation of the corresponding block-cut tree, … Read more