Contributed Session Wed.3.H 3004

Wednesday, 15:15 - 16:45 h, Room: H 3004

Cluster 2: Combinatorial optimization [...]

Knapsack and bin packing


Chair: Alantha Newman



Wednesday, 15:15 - 15:40 h, Room: H 3004, Talk 1

Alantha Newman
A counterexample to Beck's three permutations conjecture

Coauthors: Ofer Neiman, Aleksandar Nikolov


Given three permutations on the integers 1 through n, consider the
set system consisting of each interval in each of the three
permutations. In 1982, József Beck conjectured that the discrepancy
of this set system is O(1). In other words, Beck conjectured that
for every three permutations, each integer from 1 through n can be
colored either red or blue so that the number of red and blue integers
in each interval of each permutation differs only by a constant. (The
discrepancy of a set system based on two permutations is two.)
In this talk, we give a counterexample to this conjecture: for any
positive integer n = 3k, we construct three permutations whose
corresponding set system has discrepancy Ω(log{n}). Our
counterexample is based on a simple recursive construction, and our
proof of the discrepancy lower bound is by induction.
We also present implications of this construction for the bin packing
problem: There are instances of bin packing problem and corresponding
basic feasible LP solutions, such that any packing that only uses
patterns from the support of these solutions requires at least OPT + Ω{log(n)} bins.



Wednesday, 15:45 - 16:10 h, Room: H 3004, Talk 2

Paolo Detti
The bounded sequential multiple knapsack problem


The Bounded Multiple Knapsack Problem (BMKP) is a generalization of the 0-1 multiple knapsack problem, where a bounded amount of each item type is available. In this work, a special case of BMKP is considered in which the sizes of the items are divisible. This problem is known in the literature as Bounded Sequential Multiple Knapsack Problem (BSMKP). Several authors have addressed the Bounded Sequential Knapsack Problem (BSKP). Pochet and Weismantel provided a description of the bounded sequential single-knapsack polytope. Polynomial time algorithms for BSKP and BSMKP are also proposed in the literature. This work basically extends the study of Pochet and Weismantel to BSMKP. Specifically, problem transformations are proposed for BSMKP that allow a characterization of the optimal solutions and the description of the BSMKP polytope.
Keywords: bounded sequential multiknapsack, optimal solutions, polytope description.



Wednesday, 16:15 - 16:40 h, Room: H 3004, Talk 3

Joachim Schauer
Knapsack problems with disjunctive constraints

Coauthor: Ulrich Pferschy


We study the classical 0-1 knapsack problem subject to binary disjunctive constraints. Conflict constraints state that certain pairs of items cannot be simultaneously contained in a feasible solution. Forcing constraints enforce at least one of the items of each given pair to be included into the knapsack. A natural way for representing these constraints is the use of conflict (resp. forcing) graphs. We will derive FPTASs for the knapsack problem with chordal forcing graphs and with forcing graphs of bounded treewidth - complementing results for the conflict graph case given in Pferschy and Schauer (2009). The result for chordal forcing graphs is derived by a transformation of the problem into a minimization knapsack problem with chordal conflict graphs. We will furthermore give a PTAS for the knapsack problem with planar conflict graphs. In contrast the corresponding forcing graph problem is inapproximable. Similar complexity results are given for
subclasses of perfect graphs as conflict (resp. forcing) graphs.


  There are three major facts that should be watched out for in all payday loans in the United States. But at the same time, it acts only with sexual arousal. Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.