CINECA IRIS Institutional Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishWe 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 |
File in questo prodotto:
http://hdl.handle.net/11697/179741
Copyright © 2022