{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T04:10:42Z","timestamp":1746245442408},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642046445"},{"type":"electronic","value":"9783642046452"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-04645-2_25","type":"book-chapter","created":{"date-parts":[[2009,10,7]],"date-time":"2009-10-07T11:14:23Z","timestamp":1254914063000},"page":"275-286","source":"Crossref","is-referenced-by-count":17,"title":["On Profit-Maximizing Pricing for the Highway and Tollbooth Problems"],"prefix":"10.1007","author":[{"given":"Khaled","family":"Elbassioni","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rajiv","family":"Raman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saurabh","family":"Ray","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ren\u00e9","family":"Sitters","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"25_CR1","doi-asserted-by":"publisher","first-page":"1083","DOI":"10.1145\/1109557.1109677","volume-title":"SODA 2006: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm","author":"G. Aggarwal","year":"2006","unstructured":"Aggarwal, G., Hartline, J.D.: Knapsack auctions. In: SODA 2006: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pp. 1083\u20131092. ACM Press, New York (2006)"},{"key":"25_CR2","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1145\/1134707.1134711","volume-title":"EC 2006: Proceedings of the 7th ACM conference on Electronic commerce","author":"M.F. Balcan","year":"2006","unstructured":"Balcan, M.F., Blum, A.: Approximation algorithms and online mechanisms for item pricing. In: EC 2006: Proceedings of the 7th ACM conference on Electronic commerce, pp. 29\u201335. ACM Press, New York (2006)"},{"key":"25_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/978-3-540-77105-0_29","volume-title":"Internet and Network Economics","author":"M.-F. Balcan","year":"2007","unstructured":"Balcan, M.-F., Blum, A., Chan, H., Hajiaghayi, M.: A theory of loss-leaders: Making money by pricing below cost. In: Deng, X., Graham, F.C. (eds.) WINE 2007. LNCS, vol.\u00a04858, pp. 293\u2013299. Springer, Heidelberg (2007)"},{"key":"25_CR4","volume-title":"EC 2008: Proceedings of the 9th ACM conference on Electronic commerce","author":"M.F. Balcan","year":"2008","unstructured":"Balcan, M.F., Blum, A., Mansour, Y.: Item pricing for revenue maximization. In: EC 2008: Proceedings of the 9th ACM conference on Electronic commerce. ACM Press, New York (to appear) (2008)"},{"key":"25_CR5","doi-asserted-by":"publisher","first-page":"179","DOI":"10.4086\/toc.2007.v003a009","volume":"3","author":"M.F. Balcan","year":"2007","unstructured":"Balcan, M.F., Blum, A.: Approximation algorithms and online mechanisms for item pricing. Theory of Computing\u00a03, 179\u2013195 (2007)","journal-title":"Theory of Computing"},{"key":"25_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"808","DOI":"10.1007\/978-3-540-70575-8_66","volume-title":"Automata, Languages and Programming","author":"P. Briest","year":"2008","unstructured":"Briest, P.: Uniform budgets and the envy-free pricing problem. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 808\u2013819. Springer, Heidelberg (2008)"},{"unstructured":"Briest, P., Hoefer, M., Krysta, P.: Stackelberg network pricing games. In: Proc. 25th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 133\u2013142 (2008)","key":"25_CR7"},{"key":"25_CR8","doi-asserted-by":"publisher","first-page":"1093","DOI":"10.1145\/1109557.1109678","volume-title":"SODA 2006: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm","author":"P. Briest","year":"2006","unstructured":"Briest, P., Krysta, P.: Single-minded unlimited supply pricing on sparse instances. In: SODA 2006: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pp. 1093\u20131102. ACM Press, New York (2006)"},{"unstructured":"Briest, P., Krysta, P.: Buying cheap is expensive: Hardness of non-parametric multi-product pricing. In: Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM-SIAM (2007)","key":"25_CR9"},{"doi-asserted-by":"crossref","unstructured":"Cheung, M., Swamy, C.: Approximation algorithms for single-minded envy-free profit-maximization problems with limited supply. In: FOCS 2008, pp. 35\u201344 (2008)","key":"25_CR10","DOI":"10.1109\/FOCS.2008.15"},{"key":"25_CR11","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1145\/1109557.1109577","volume-title":"SODA 2006: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm","author":"E.D. Demaine","year":"2006","unstructured":"Demaine, E.D., Hajiaghayi, M.T., Feige, U., Salavatipour, M.R.: Combination can be hard: approximability of the unique coverage problem. In: SODA 2006: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pp. 162\u2013171. ACM Press, New York (2006)"},{"key":"25_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/978-3-540-75520-3_41","volume-title":"Algorithms \u2013 ESA 2007","author":"K.M. Elbassioni","year":"2007","unstructured":"Elbassioni, K.M., Sitters, R.A., Zhang, Y.: A quasi-PTAS for profit-maximizing pricing on line graphs. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol.\u00a04698, pp. 451\u2013462. Springer, Heidelberg (2007)"},{"issue":"1","key":"25_CR13","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1287\/opre.1050.0252","volume":"54","author":"P.W. Glynn","year":"2006","unstructured":"Glynn, P.W., Van Roy, B., Rusmevichientong, P.: A nonparametric approach to multi-product pricing. Operations Research\u00a054(1), 82\u201398 (2006)","journal-title":"Operations Research"},{"doi-asserted-by":"crossref","unstructured":"Golovin, D., Nagarajan, V., Singh, M.: Approximating the k-multicut problem. In: SODA 2006, pp. 621\u2013630 (2006)","key":"25_CR14","DOI":"10.1145\/1109557.1109625"},{"key":"25_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/11917496_12","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"A. Grigoriev","year":"2006","unstructured":"Grigoriev, A., van Loon, J., Sitters, R., Uetz, M.: How to sell a graph: Guidelines for graph retailers. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol.\u00a04271, pp. 125\u2013136. Springer, Heidelberg (2006)"},{"unstructured":"Guruswami, V., Hartline, J.D., Karlin, A.R., Kempe, D., Kenyon, C., McSherry, F.: On profit-maximizing envy-free pricing. In: SODA 2005: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA, pp. 1164\u20131173. Society for Industrial and Applied Mathematics (2005)","key":"25_CR16"},{"key":"25_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1007\/11534273_37","volume-title":"Algorithms and Data Structures","author":"J.D. Hartline","year":"2005","unstructured":"Hartline, J.D., Koltun, V.: Near-optimal pricing in near-linear time. In: Dehne, F., L\u00f3pez-Ortiz, A., Sack, J.-R. (eds.) WADS 2005. LNCS, vol.\u00a03608, pp. 422\u2013431. Springer, Heidelberg (2005)"},{"doi-asserted-by":"crossref","unstructured":"Khandekar, R., Kimbrel, T., Makarychev, K., Sviridenko, M.: On hardness of pricing items for single-minded bidders. In: Proceedings, 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX (2009)","key":"25_CR18","DOI":"10.1007\/978-3-642-03685-9_16"},{"issue":"4","key":"25_CR19","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1561\/0400000009","volume":"1","author":"M. Luby","year":"2005","unstructured":"Luby, M., Wigderson, A.: Pairwise independence and derandomization. Foundations and Trends in Theoretical Computer Science\u00a01(4), 237\u2013301 (2005)","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"25_CR20","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized algorithms. Cambridge University Press, Cambridge (1995)"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Game Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04645-2_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T16:26:47Z","timestamp":1558283207000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04645-2_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642046445","9783642046452"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04645-2_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}