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 .
New bounds for the balloon popping problem / Bilò, Davide; Bilo', Vittorio. - In: JOURNAL OF COMBINATORIAL OPTIMIZATION. - ISSN 1382-6905. - 29:1(2015), pp. 182-196. [10.1007/s10878-013-9696-7]
New bounds for the balloon popping problem
BILÒ, Davide;
2015-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(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 .I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.