{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T09:34:21Z","timestamp":1725701661492},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642330896"},{"type":"electronic","value":"9783642330902"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33090-2_31","type":"book-chapter","created":{"date-parts":[[2012,8,28]],"date-time":"2012-08-28T15:29:11Z","timestamp":1346167751000},"page":"349-360","source":"Crossref","is-referenced-by-count":2,"title":["A Path-Decomposition Theorem with Applications to Pricing and Covering on Trees"],"prefix":"10.1007","author":[{"given":"Marek","family":"Cygan","sequence":"first","affiliation":[]},{"given":"Fabrizio","family":"Grandoni","sequence":"additional","affiliation":[]},{"given":"Stefano","family":"Leonardi","sequence":"additional","affiliation":[]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[]},{"given":"Piotr","family":"Sankowski","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"31_CR1","doi-asserted-by":"crossref","unstructured":"Balcan, M.-F., Blum, A.: Approximation algorithms and online mechanisms for item pricing. In: ACM Conference on Electronic Commerce, pp. 29\u201335 (2006)","DOI":"10.1145\/1134707.1134711"},{"key":"31_CR2","doi-asserted-by":"crossref","unstructured":"Bansal, N., Chakrabarti, A., Epstein, A., Schieber, B.: A quasi-PTAS for unsplittable flow on line graphs. In: ACM Symposium on Theory of Computing (STOC), pp. 721\u2013729 (2006)","DOI":"10.1145\/1132516.1132617"},{"key":"31_CR3","doi-asserted-by":"crossref","unstructured":"Briest, P., Krysta, P.: Single-minded unlimited supply pricing on sparse instances. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1093\u20131102 (2006)","DOI":"10.1145\/1109557.1109678"},{"issue":"4","key":"31_CR4","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.T., Salavatipour, M.R.: Combination can be hard: Approximability of the unique coverage problem. SIAM Journal on Computing\u00a038(4), 1464\u20131483 (2008)","journal-title":"SIAM Journal on Computing"},{"key":"31_CR5","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":"31_CR6","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)"},{"key":"31_CR7","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":"31_CR8","doi-asserted-by":"crossref","unstructured":"Grandoni, F., Rothvo\u00df, T.: Pricing on paths: A ptas for the highway problem. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 675\u2013684 (2011)","DOI":"10.1137\/1.9781611973082.53"},{"key":"31_CR9","unstructured":"Guruswami, V., Hartline, J.D., Karlin, A.R., Kempe, D., Kenyon, C., McSherry, F.: On profit-maximizing envy-free pricing. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1164\u20131173 (2005)"},{"key":"31_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/11538462_9","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"V. Guruswami","year":"2005","unstructured":"Guruswami, V., Trevisan, L.: The Complexity of Making Unique Choices: Approximating 1-in-k SAT. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX 2005 and RANDOM 2005. LNCS, vol.\u00a03624, pp. 99\u2013110. Springer, Heidelberg (2005)"},{"key":"31_CR11","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":"31_CR12","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":"31_CR13","doi-asserted-by":"crossref","unstructured":"Popat, P., Wu, Y.: On the hardness of pricing loss-leaders. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 735\u2013749 (2012)","DOI":"10.1137\/1.9781611973099.60"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33090-2_31.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:54:53Z","timestamp":1620129293000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33090-2_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642330896","9783642330902"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33090-2_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}