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 fixed-price scheme. Previous works show that the optimal solution for this problem is in the range [1.6595,2]. We give a new lower bound of 1.68 and design an O(n 5) 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 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 π 2/6 + 1/4 ≈ 1.8949. © 2013 Springer-Verlag Berlin Heidelberg.
|Titolo:||New bounds for the balloon popping problem|
|Data di pubblicazione:||2013|
|Appare nelle tipologie:||4.1 Contributo in Atti di convegno|