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" [...]


  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.