A Sublogarithmic Approximation for Tollbooth Pricing on Trees

References

• Aggarwal G, Feder T, Motwani R, Zhu A (2004) Algorithms for multi-product pricing. Diaz J, Karhümaki J, Lepistö A, Sannella D, eds. Proc. 31st Internat. Colloquium on Automata, Languages and Programming, ICALP ’04 (Springer, Berlin), 72–83.Crossref, Google Scholar
• Aggarwal G, Fiat A, Goldberg AV, Hartline JD, Immorlica N, Sudan M (2011) Derandomization of auctions. Games Econom. Behav. 72(1):1–11.Crossref, Google Scholar
• Alon N, Spencer JH (2000) The Probabilistic Method, second ed. (John Wiley & Sons, New York).Crossref, Google Scholar
• Balcan MF, Blum A (2007) Approximation algorithms and online mechanisms for item pricing. Theory Comput. 3(1):179–195.Crossref, Google Scholar
• Balcan M-F, Blum A, Mansour Y (2008) Item pricing for revenue maximization. SIGecom Exchanges 7(3):article 6.Crossref, Google Scholar
• Bansal N, Chen N, Cherniavsky N, Rudra A, Schieber B, Sviridenko M (2010) Dynamic pricing for impatient bidders. ACM Trans. Algorithms 6(2):article 35.Crossref, Google Scholar
• Briest P (2008) Uniform budgets and the envy-free pricing problem. Aceto L, Damgárd I, Goldberg LA, Halldórsson MM, Ingólfsdóttir A, Walukiewicz I, eds. Proc. 35th Internat. Colloquium on Automata, Languages and Programming, ICALP ’08 (Springer, Berlin), 808–819.Crossref, Google Scholar
• Briest P, Krysta P (2006) Single-minded unlimited supply pricing on sparse instances. Proc. 17th Annual ACM-SIAM Sympos. Discrete Algorithms, SODA ’06 (ACM, New York), 1093–1102.Crossref, Google Scholar
• Briest P, Krysta P (2011) Buying cheap is expensive: Approximability of combinatorial pricing problems. SIAM J. Comput. 40(6):1554–1586.Crossref, Google Scholar
• Chawla S, Hartline JD, Kleinberg RD (2007) Algorithmic pricing via virtual valuations. MacKie-Mason JK, Parkes DC, Resnick P, eds. Proc. 8th ACM Conf. Electronic Commerce, EC ’07 (ACM, New York), 243–251.Crossref, Google Scholar
• Chen N, Ghosh A, Vassilvitskii S (2011) Optimal envy-free pricing with metric substitutability. SIAM J. Comput. 40(3):623–645.Crossref, Google Scholar
• Cheung M, Swamy C (2008) Approximation algorithms for single-minded envy-free profit-maximization problems with limited supply. Proc. 49th Annual IEEE Sympos. Foundations Comput. Sci., FOCS ’08 (IEEE Computer Society, Washington, DC), 35–44.Crossref, Google Scholar
• Cygan M, Grandoni F, Leonardi S, Pilipczuk M, Sankowski P (2012) A path-decomposition theorem with applications to pricing and covering on trees. Epstein L, Ferragina P, eds. Proc. 20th Annual Eur. Sympos. Algorithms (Springer, Berlin), 349–360.Crossref, Google Scholar
• Demaine ED, Feige U, Hajiaghayi M, Salavatipour MR (2008) Combination can be hard: Approximability of the unique coverage problem. SIAM J. Comput. 38(4):1464–1483.Crossref, Google Scholar
• Elbassioni KM, Sitters R, Zhang Y (2007) A quasi-PTAS for profit-maximizing pricing on line graphs. Proc. 15th Annual Eur. Sympos. Algorithms, 451–462.Crossref, Google Scholar
• Elbassioni KM, Raman R, Ray S, Sitters R (2009) On profit-maximizing pricing for the highway and tollbooth problems. Arge L, Hoffmann M, Welzl E, eds. Proc. 2nd Internat. Sympos. Algorithmic Game Theory (Springer, Berlin), 275–286.Crossref, Google Scholar
• Elberfeld M, Bafna V, Gamzu I, Medvedovsky A, Segev D, Silverbush D, Zwick U, Sharan R (2011) On the approximability of reachability-preserving network orientations. Internet Math., Special Issue on Biol. Networks 7(4):209–232.Google Scholar
• Even G, Garg N, Könemann J, Ravi R, Sinha A (2004) Min-max tree covers of graphs. Oper. Res. Lett. 32(4):309–315.Crossref, Google Scholar
• Frederickson GN, Johnson DB (1983) Finding k-th paths and p-centers by generating and searching good data structures. J. Algorithms 4(1):61–80.Crossref, Google Scholar
• Gamzu I, Segev D (2010) A sublogarithmic approximation for highway and tollbooth pricing. Abramsky S, Gavoille C, Kirchner C, Meyer auf der Heide F, Spirakis PG, eds. Proc. 37th Internat. Colloquium on Automata, Languages and Programming, ICALP ’10 (Springer, Berlin), 582–593.Crossref, Google Scholar
• Goldberg AV, Hartline JD, Karlin AR, Saks M, Wright A (2006) Competitive auctions. Games Econom. Behav. 55(2):242–269.Crossref, Google Scholar
• Goldschmidt O, Hochbaum DS, Levin A, Olinick EV (2003) The SONET edge-partition problem. Networks 41(1):13–23.Crossref, Google Scholar
• Grandoni F, Rothvoß T (2011) Pricing on paths: A PTAS for the highway problem. Randall D, ed. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 675–684.Crossref, Google Scholar
• Grigoriev A, van Loon J, Sviridenko M, Uetz M, Vredeveld T (2007) Bundle pricing with comparable items. Arge L, Hoffmann M, Welzl E, eds. Proc. 15th Annual Eur. Sympos. Algorithms (Springer, Berlin), 475–486.Crossref, Google Scholar
• Grigoriev A, van Loon J, Sviridenko M, Uetz M, Vredeveld T (2008) Optimal bundle pricing with monotonicity constraint. Oper. Res. Lett. 36(5):609–614.Crossref, Google Scholar
• Guruswami V, Hartline JD, Karlin AR, Kempe D, Kenyon C, McSherry F (2005) On profit-maximizing envy-free pricing. Proc. 16th Annual ACM-SIAM Sympos. Discrete Algorithms, SODA ’07 (SIAM, Philadelphia), 1164–1173.Google Scholar
• Hartline JD, Koltun V (2005) Near-optimal pricing in near-linear time. Proc. 9th Internat. Workshop on Algorithms and Data Structures, 422–431.Crossref, Google Scholar
• Hassin R, Segev D (2006) Robust subgraphs for trees and paths. ACM Trans. Algorithms 2(2):263–281.Crossref, Google Scholar
• Khandekar R, Kimbrel T, Makarychev K, Sviridenko M (2009) On hardness of pricing items for single-minded bidders. Dinur I, Jansen K, Naor J, Rolim JDP, eds. Proc. 12th Internat. Workshop on Approximation Algorithms for Combinatorial Optim. Problems, APPROX ’09 (Springer, Berlin), 202–216.Crossref, Google Scholar
• Krauthgamer R, Mehta A, Rudra A (2011) Pricing commodities. Theoret. Comput. Sci. 412(7):602–613.Crossref, Google Scholar