{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:56:04Z","timestamp":1725558964429},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642141645"},{"type":"electronic","value":"9783642141652"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"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":[[2010]]},"DOI":"10.1007\/978-3-642-14165-2_49","type":"book-chapter","created":{"date-parts":[[2010,7,5]],"date-time":"2010-07-05T09:26:02Z","timestamp":1278321962000},"page":"582-593","source":"Crossref","is-referenced-by-count":10,"title":["A Sublogarithmic Approximation for Highway and Tollbooth Pricing"],"prefix":"10.1007","author":[{"given":"Iftah","family":"Gamzu","sequence":"first","affiliation":[]},{"given":"Danny","family":"Segev","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"49_CR1","doi-asserted-by":"crossref","DOI":"10.1002\/0471722154","volume-title":"The Probabilistic Method","author":"N. Alon","year":"2000","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method, 2nd edn. Wiley, New York (2000)","edition":"2"},{"issue":"1","key":"49_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":"49_CR3","doi-asserted-by":"crossref","unstructured":"Balcan, M.F., Blum, A., Mansour, Y.: Item pricing for revenue maximization. In: EC, pp. 50\u201359 (2008)","DOI":"10.1145\/1386790.1386802"},{"key":"49_CR4","doi-asserted-by":"crossref","unstructured":"Briest, P., Krysta, P.: Single-minded unlimited supply pricing on sparse instances. In: SODA, pp. 1093\u20131102 (2006)","DOI":"10.1145\/1109557.1109678"},{"key":"49_CR5","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 (2008)","DOI":"10.1109\/FOCS.2008.15"},{"issue":"4","key":"49_CR6","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 Journal of Computing\u00a038(4), 1464\u20131483 (2008)","journal-title":"SIAM Journal of Computing"},{"key":"49_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/978-3-642-04645-2_25","volume-title":"SAGT 2009","author":"K.M. Elbassioni","year":"2009","unstructured":"Elbassioni, K.M., 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":"49_CR8","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., 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":"49_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1007\/978-3-540-45198-3_3","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"G. Even","year":"2003","unstructured":"Even, G., Garg, N., K\u00f6nemann, J., Ravi, R., Sinha, A.: Covering graphs using trees and stars. In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) RANDOM 2003 and APPROX 2003. LNCS, vol.\u00a02764, pp. 24\u201335. Springer, Heidelberg (2003)"},{"key":"49_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/3-540-10003-2_73","volume-title":"Automata, Languages and Programming","author":"G.N. Frederickson","year":"1980","unstructured":"Frederickson, G.N., Johnson, D.B.: Generating and searching sets induced by networks. In: de Bakker, J.W., van Leeuwen, J. (eds.) ICALP 1980. LNCS, vol.\u00a085, pp. 221\u2013233. Springer, Heidelberg (1980)"},{"key":"49_CR11","unstructured":"Gamzu, I., Segev, D.: A sublogarithmic approximation for highway and tollbooth pricing, \n                    \n                      http:\/\/arxiv.org\/abs\/1002.2084"},{"key":"49_CR12","unstructured":"Gamzu, I., Segev, D.: An improved approximation algoritm for maximum graph orientation (2010) (in preparation)"},{"key":"49_CR13","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":"49_CR14","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)"},{"issue":"2","key":"49_CR15","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1145\/1150334.1150341","volume":"2","author":"R. Hassin","year":"2006","unstructured":"Hassin, R., Segev, D.: Robust subgraphs for trees and paths. ACM Transactions on Algorithms\u00a02(2), 263\u2013281 (2006)","journal-title":"ACM Transactions on Algorithms"},{"key":"49_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1007\/978-3-642-03685-9_16","volume-title":"APPROX 2009","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 2009. LNCS, vol.\u00a05687, pp. 202\u2013216. Springer, Heidelberg (2009)"},{"key":"49_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-77918-6_1","volume-title":"Approximation and Online Algorithms","author":"R. Krauthgamer","year":"2008","unstructured":"Krauthgamer, R., Mehta, A., Rudra, A.: Pricing commodities, or how to sell when buyers have restricted valuations. In: Kaklamanis, C., Skutella, M. (eds.) WAOA 2007. LNCS, vol.\u00a04927, pp. 1\u201314. Springer, Heidelberg (2008)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14165-2_49","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T15:40:16Z","timestamp":1558280416000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14165-2_49"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642141645","9783642141652"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14165-2_49","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}