Approximation Algorithms and Online Mechanisms for Item Pricing

by Maria-Florina Balcan and Avrim Blum

Theory of Computing, Volume 3(9), pp. 179-195, 2007

Bibliography with links to cited articles

[1] B. Awerbuch and R. Kleinberg: Adaptive routing with end-to-end feedback: Distributed learning and geometric approaches. In Proc. 36th STOC, pp. 45-53. ACM Press, 2004. [STOC:1007352.1007367].
[2] M.-F. Balcan, A. Blum, H. Chan, and M.T. Hajiaghayi: A theory of loss-leaders: Making money by pricing below cost. In Proc. 3rd Intern. Workshop on Internet and Network Economics, Lecture Notes in Computer Science. Springer, 2007.
[3] M.-F. Balcan, A. Blum, J. Hartline, and Y. Mansour: Mechanism design via machine learning. In Proc. 46th FOCS, pp. 605-614. IEEE Computer Soc., 2005. [FOCS:10.1109/SFCS.2005.50].
[4] M.-F. Balcan, A. Blum, and Y. Mansour: Single price mechanisms for revenue maximization in unlimited supply combinatorial auctions. Technical Report CMU-CS-07-111, Carnegie Mellon University, 2007. [ .pdf ]
[5] A. Blum and J. Hartline: Near-optimal online auctions. In Proc. 16th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA'05), pp. 1156-1163. SIAM, 2005. [SODA:1070432.1070597].
[6] A. Blum, V. Kumar, A. Rudra, and F. Wu: Online learning in online auctions. In Proc. 14th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA'03), pp. 202-204. SIAM, 2003. [SODA:644108.644143].
[7] P. Briest and P. Krysta: Single-minded unlimited supply pricing on sparse instances. In Proc. 17th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA'06), pp. 1093-1102. SIAM, 2006. [SODA:1109557.1109678].
[8] P. Briest and P. Krysta: Buying cheap is expensive: Hardness of non-parametric multi-product pricing. In Proc. 18th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA'07), pp. 716-725. SIAM, 2007. [SODA:1283383.1283460].
[9] V. Dani and T. P. Hayes: Robbing the bandit: Less regret in online geometric optimization against an adaptive adversary. In Proc. 17th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA'06), pp. 937-943. SIAM, 2006. [SODA:1109557.1109660].
[10] E. D. Demaine, U. Feige, M. Hajiaghayi, and M. R. Salavatipour: Combination can be hard: Approximability of the unique coverage problem. In Proc. 17th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA'06), pp. 162-171. SIAM, 2006. [SODA:1109557.1109577].
[11] K. Elbassioni, R. Sitters, and Y. Zhang: A quasi-PTAS for profit-maximizing pricing on line graphs. In Proc. 15th Ann. European Symp. on Algorithms (ESA'07), Lecture Notes in Computer Science. Springer, 2007.
[12] G. Even, O. Goldreich, M. Luby, N. Nisan, and B. Velickovic: Efficient approximation of product distributions. Random Structures and Algorithms, 13(1):1-16, 1998. [Wiley:10.1002/(SICI)1098-2418(199808)13:1<1::AID-RSA1>3.0.CO;2-W].
[13] A. Goldberg, J. Hartline, A. Karlin, M. Saks, and A. Wright: Competitive auctions. Games and Economic Behavior, 55(2):242-269, 2006. [Elsevier:10.1016/j.geb.2006.02.003].
[14] A. Goldberg, J. Hartline, and A. Wright: Competitive auctions and digital goods. In Proc. 12th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA'01), pp. 735-744. SIAM, 2001. [SODA:365411.365768].
[15] V. Guruswami, J. Hartline, A. Karlin, D. Kempe, C. Kenyon, and F. McSherry: On profit-maximizing envy-free pricing. In Proc. 16th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA'05), pp. 1164-1173. SIAM, 2005. [SODA:1070432.1070598].
[16] J. Hartline and V. Koltun: Near-optimal pricing in near-linear time. In 9th Workshop on Algorithms and Data Structures (WADS'05), number 3608 in Lecture Notes in Computer Science, pp. 422-431. Springer, 2005. [WADS:al2ke8gd23a44atp].
[17] S. Kakade, A. Kalai, and K. Ligett: Playing games with approximation algorithms. In Proc. 39th STOC, pp. 546-555. ACM Press, 2007. [STOC:1250790.1250870].
[18] A. Kalai and S. Vempala: Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):291-307, 2005. An earlier version appears in COLT 2003. [JCSS:10.1016/j.jcss.2004.10.016, Springer:fbx1n68j5ubyv706].
[19] R. Krauthgamer, A. Mehta, and A. Rudra: Pricing commodities, or how to sell when buyers have restricted valuations. In 5th Workshop on Approximation and Online Algorithms. Springer, 2007.
[20] M. Luby and A. Wigderson: Pairwise independence and derandomization. Technical Report CSD-95-880, U.C. Berkeley, 1995.
[21] H. B. McMahan and A. Blum: Online geometric optimization in the bandit setting against an adaptive adversary. In Proc. 17th Conf. on Computational Learning Theory (COLT'04), number 3120 in Lecture Notes in Computer Science, pp. 109-123. Springer, 2004. [Springer:38p3f4h61cgy7gg7].
[22] R. Motwani and P. Raghavan: Randomized Algorithms. Cambridge University Press, 1995.

This file has been generated by bibtex2html 1.85.