New bounds for the balloon popping problem

Davide Bilò () and Vittorio Bilò ()
Additional contact information
Davide Bilò: University of Sassari
Vittorio Bilò: University of Salento

Journal of Combinatorial Optimization, 2015, vol. 29, issue 1, No 11, 182-196

Abstract: 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$$ 1.68 and design an $$O(n^5)$$ O ( n 5 ) algorithm for computing upper bounds as a function of the number of bidders $$n$$ n . Our algorithm provides an experimental evidence that the correct upper bound is a constant smaller than $$2$$ 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 $$\pi ^2/6+1/4\approx 1.8949$$ π 2 / 6 + 1 / 4 ≈ 1.8949 .

Keywords: Approximation algorithms; Online algorithms; Combinatorial optimization; Auction theory (search for similar items in EconPapers)
Date: 2015
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-013-9696-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:29:y:2015:i:1:d:10.1007_s10878-013-9696-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-013-9696-7

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().