{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T16:44:31Z","timestamp":1787503471398,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642325113","type":"print"},{"value":"9783642325120","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32512-0_7","type":"book-chapter","created":{"date-parts":[[2012,7,20]],"date-time":"2012-07-20T18:21:08Z","timestamp":1342808468000},"page":"73-84","source":"Crossref","is-referenced-by-count":24,"title":["Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply"],"prefix":"10.1007","author":[{"given":"Parinya","family":"Chalermsook","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Julia","family":"Chuzhoy","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sampath","family":"Kannan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"7_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1007\/978-3-540-27836-8_9","volume-title":"Automata, Languages and Programming","author":"G. Aggarwal","year":"2004","unstructured":"Aggarwal, G., Feder, T., Motwani, R., Zhu, A.: Algorithms for Multi-product Pricing. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 72\u201383. Springer, Heidelberg (2004)"},{"issue":"1","key":"7_CR2","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(1), 179\u2013195 (2007)","journal-title":"Theory of Computing"},{"key":"7_CR3","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)"},{"key":"7_CR4","unstructured":"Briest, P., Krysta, P.: Buying cheap is expensive: hardness of non-parametric multi-product pricing. In: SODA, pp. 716\u2013725 (2007)"},{"key":"7_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1007\/978-3-642-14162-1_35","volume-title":"Automata, Languages and Programming","author":"N. Chen","year":"2010","unstructured":"Chen, N., Deng, X.: Envy-Free Pricing in Multi-item Markets. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010, Part II. LNCS, vol.\u00a06199, pp. 418\u2013429. Springer, Heidelberg (2010)"},{"issue":"3","key":"7_CR6","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1137\/080740970","volume":"40","author":"N. Chen","year":"2011","unstructured":"Chen, N., Ghosh, A., Vassilvitskii, S.: Optimal envy-free pricing with metric substitutability. SIAM J. Comput.\u00a040(3), 623\u2013645 (2011)","journal-title":"SIAM J. Comput."},{"key":"7_CR7","doi-asserted-by":"crossref","unstructured":"Cheung, M., Swamy, C.: Approximation algorithms for single-minded envy-free profit-maximization problems with limited supply. In: FOCS, pp. 35\u201344. IEEE Computer Society (2008)","DOI":"10.1109\/FOCS.2008.15"},{"issue":"4","key":"7_CR8","doi-asserted-by":"publisher","first-page":"1464","DOI":"10.1137\/060656048","volume":"38","author":"E.D. Demaine","year":"2008","unstructured":"Demaine, E.D., Feige, U., Hajiaghayi, M., Salavatipour, M.R.: Combination can be hard: Approximability of the unique coverage problem. SIAM J. Comput.\u00a038(4), 1464\u20131483 (2008)","journal-title":"SIAM J. Comput."},{"key":"7_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/978-3-642-04645-2_25","volume-title":"Algorithmic Game Theory","author":"K. Elbassioni","year":"2009","unstructured":"Elbassioni, K., Raman, R., Ray, S., Sitters, R.: On Profit-Maximizing Pricing for the Highway and Tollbooth Problems. In: Mavronicolas, M., Papadopoulou, V.G. (eds.) SAGT 2009. LNCS, vol.\u00a05814, pp. 275\u2013286. Springer, Heidelberg (2009)"},{"key":"7_CR10","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. Elbassioni","year":"2007","unstructured":"Elbassioni, K., Sitters, R., 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)"},{"key":"7_CR11","doi-asserted-by":"crossref","unstructured":"Feige, U.: Relations between average case complexity and approximation complexity. In: STOC, pp. 534\u2013543 (2002)","DOI":"10.1145\/509984.509985"},{"key":"7_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"582","DOI":"10.1007\/978-3-642-14165-2_49","volume-title":"Automata, Languages and Programming","author":"I. Gamzu","year":"2010","unstructured":"Gamzu, I., Segev, D.: A Sublogarithmic Approximation for Highway and Tollbooth Pricing. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010, Part I. LNCS, vol.\u00a06198, pp. 582\u2013593. Springer, Heidelberg (2010)"},{"key":"7_CR13","doi-asserted-by":"crossref","unstructured":"Grandoni, F., Rothvo\u00df, T.: Pricing on paths: A ptas for the highway problem. In: SODA, pp. 675\u2013684 (2011)","DOI":"10.1137\/1.9781611973082.53"},{"key":"7_CR14","unstructured":"Guruswami, V., Hartline, J.D., Karlin, A.R., Kempe, D., Kenyon, C., McSherry, F.: On profit-maximizing envy-free pricing. In: SODA, pp. 1164\u20131173 (2005)"},{"key":"7_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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)"},{"key":"7_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1007\/978-3-642-03685-9_16","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"R. Khandekar","year":"2009","unstructured":"Khandekar, R., Kimbrel, T., Makarychev, K., Sviridenko, M.: On Hardness of Pricing Items for Single-Minded Bidders. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX and RANDOM 2009. LNCS, vol.\u00a05687, pp. 202\u2013216. Springer, Heidelberg (2009)"},{"key":"7_CR17","doi-asserted-by":"publisher","first-page":"767","DOI":"10.1145\/509907.510017","volume-title":"Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing, STOC 2002","author":"S. Khot","year":"2002","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing, STOC 2002, pp. 767\u2013775. ACM, New York (2002)"},{"key":"7_CR18","unstructured":"Rusmevichientong, P.: A non-parametric approach to multi-product pricing: Theory and application. Ph. D. thesis, Stanford University (2003)"},{"key":"7_CR19","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1287\/opre.1050.0252","volume":"54","author":"P. Rusmevichientong","year":"2006","unstructured":"Rusmevichientong, P., Van Roy, B., Glynn, P.W.: A nonparametric approach to multiproduct pricing. Oper. Res.\u00a054, 82\u201398 (2006)","journal-title":"Oper. Res."},{"key":"7_CR20","doi-asserted-by":"crossref","unstructured":"Trevisan, L.: Non-approximability results for optimization problems on bounded degree instances. In: STOC, pp. 453\u2013461 (2001)","DOI":"10.1145\/380752.380839"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32512-0_7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T08:05:42Z","timestamp":1620115542000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32512-0_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642325113","9783642325120"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32512-0_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}