A Branch and Bound algorithm for the minimax regret spanning arborescence

The paper considers the problem of finding a spanning arborescence on a directed network whose arc costs are partially known. It is assumed that each arc cost can take on values from a known interval defining a possible economic scenario. In this context, the problem of finding the spanning arborescence which better approaches to that of minimum overall cost under each possible scenario is studied. The minimax regret criterion is proposed in order to obtain such a robust solution of the problem. As it is shown, the bounds on the optimal value of the minimax regret optimization problem obtained in a previous paper, can be used here in a Branch and Bound algorithm in order to give an optimal solution. The computational behavior of the algorithm is tested through numerical experiments. This research has been supported by the Spanish Ministry of Education and Science and FEDER Grant No. MTM2006-04393 and by the European Alfa Project, “Engineering System for Preparing and Making Decisions Under Multiple Criteria”, II-0321-FA.     

Compact storage schemes for formatted files by spanning trees

The use of spanning trees in the compression of data files is studied. A new upper bound for the length of the minimal spanning tree, giving the size of the compressed file, is derived. A special front compression technique is proposed for unordered files. The space demands are compared to an information theoretical lower bound of the file size.     

Notes on sequentially connected spaces

Summary We discuss the relationship between two different sequential connectedness, and prove that sequential connectedness is countably multiplicative.     

On cut completions of abelian lattice ordered groups

We denote by F _a the class of all abelian lattice ordered groups H such that each disjoint subset of H is finite. In this paper we prove that if G F _a, then the cut completion of G coincides with the Dedekind completion of G.     

A 3/4-Approximation Algorithm for Multiple Subset Sum

The Multiple Subset Sum Problem (MSSP) is the variant of bin packing in which the number of bins is given and one would like to maximize the overall weight of the items packed in the bins. The problem is also a special case of the multiple knapsack problem in which all knapsacks have the same capacity and the item profits and weights coincide. Recently, polynomial time approximation schemes have been proposed for MSSP and its generalizations, see A. Caprara, H. Kellerer, and U. Pferschy (SIAM J. on Optimization, Vol. 11, pp. 308–319, 2000; Information Processing Letters, Vol. 73, pp. 111–118, 2000), C. Chekuri and S. Khanna (Proceedings of SODA 00, 2000, pp. 213–222), and H. Kellerer (Proceedings of APPROX, 1999, pp. 51–62). However, these schemes are only of theoretical interest, since they require either the solution of huge integer linear programs, or the enumeration of a huge number of possible solutions, for any reasonable value of required accuracy. In this paper, we present a polynomial-time 3/4-approximation algorithm which runs fast also in practice. Its running time is linear in the number of items and quadratic in the number of bins. The core of the algorithm is a procedure to pack triples of large items into the bins. As a byproduct of our analysis, we get the approximation guarantee for a natural greedy heuristic for the 3-Partitioning Problem.