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.
New bounds for the balloon popping problem / Bilò, Davide; Bilo', Vittorio. - 7936:(2013), pp. 5-16. (Intervento presentato al convegno 19th International Conference on Computing and Combinatorics nel 21-23/06/2013) [10.1007/978-3-642-38768-5_3].
New bounds for the balloon popping problem
BILÒ, Davide;
2013-01-01
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 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
