## 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**

**Abstract:**

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 = 3*^{k}, 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

**Abstract:**

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**

**Abstract:**

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.