Authors: Davide Bilò Vittorio Bilò
Publish Date: 2013/12/12
Volume: 29, Issue: 1, Pages: 182-196
Abstract
We reconsider the balloon popping problem an intriguing combinatorial problem introduced in order to bound the competitiveness of ascending auctions with anonymous bidders with respect to the best fixedprice scheme Previous works show that the optimal solution for this problem is in the range 165952 We give a new lower bound of 168 and design an On5 algorithm for computing upper bounds as a function of the number of bidders n Our algorithm provides an experimental evidence that the correct upper bound is a constant smaller than 2 thus disproving a currently believed conjecture and can be used to test the validity of a new conjecture we propose according to which the upper bound would decrease to pi 2/6+1/4approx 18949
Keywords: