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(n5) 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 π2/6+1/4≈1.8949.
Titolo: | New bounds for the balloon popping problem | |
Autori: | ||
Data di pubblicazione: | 2015 | |
Rivista: | ||
Handle: | http://hdl.handle.net/11697/179741 | |
Appare nelle tipologie: | 1.1 Articolo in rivista |