[CSDM] [pvsnp-all] Theory lunch - TODAY - 12pm at room 402.

[Zeev Dvir]

(The original announcement was sent only to theory-read. Apologies to
everyone that did not get it).

Speaker: Alantha Newman

Title: Beck's Three Permutations Conjecture: A Counterexample and Some
Consequences


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, Beck conjectured that the discrepancy
of this set system is O(1).  In other words, the conjecture says
that 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
permutations differs only by a constant.  (The discrepancy of a set
system based on two permutations is at most two.)

We will present a counterexample to this conjecture: for any
positive integer n = 3^k, we construct three permutations whose
corresponding set system has discrepancy Omega(log(n)).

Our work was inspired by an intriguing paper from SODA 2011 by
Eisenbrand, Palvolgyi and Rothvoss, who show a surprising connection
between the discrepancy of three permutations and the bin packing
problem: They show that Beck's conjecture implies a constant
worst-case bound on the additive integrality gap for the
Gilmore-Gomory LP relaxation for bin packing in the special case when
all items have sizes strictly between 1/4 and 1/2, also known as the
three partition problem.  Our counterexample shows that this approach
to bounding the additive integrality gap for bin packing will not
work.  We can, however, prove an interesting implication of our
construction in the reverse direction: there are instances of bin
packing and corresponding optimal basic feasible solutions for the
Gilmore-Gomory LP relaxation such that any packing that contains only
patterns from the support of these solutions requires at least OPT +
Omega(log(m)) bins, where m is the number of items.

Joint work with Ofer Neiman and Aleksandar Nikolov.
_______________________________________________
pvsnp-all mailing list
pvsnp-all at lists.cs.princeton.edu
https://lists.cs.princeton.edu/mailman/listinfo/pvsnp-all