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


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.


Talk 1 of the contributed session Wed.3.H 3004
"Knapsack and bin packing" [...]
Cluster 2
"Combinatorial optimization" [...]


  Illinois Loans Online should not be obtained by people who do not have the capacity to repay the lenders. In this section we give only a brief summary recommendation for admission of Levitra. Full information can be found in the instructions for receiving medications with vardenafil.