{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:14:52Z","timestamp":1759637692286},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642041273"},{"type":"electronic","value":"9783642041280"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","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-04128-0_3","type":"book-chapter","created":{"date-parts":[[2009,9,14]],"date-time":"2009-09-14T14:16:36Z","timestamp":1252937796000},"page":"23-34","source":"Crossref","is-referenced-by-count":10,"title":["Improved Approximation Algorithms for Label Cover Problems"],"prefix":"10.1007","author":[{"given":"Moses","family":"Charikar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MohammadTaghi","family":"Hajiaghayi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Howard","family":"Karloff","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"3_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-74208-1_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"A. Aazami","year":"2007","unstructured":"Aazami, A., Stilp, M.D.: Approximation algorithms and hardness for domination with propagation. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) RANDOM 2007 and APPROX 2007. LNCS, vol.\u00a04627, pp. 1\u201315. Springer, Heidelberg (2007)"},{"key":"3_CR2","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1006\/jcss.1997.1472","volume":"54","author":"S. Arora","year":"1997","unstructured":"Arora, S., Babai, L., Stern, J., Sweedyk, Z.: The hardness of approximate optima in lattices, codes, and systems of linear equations. J. Comput. System Sci.\u00a054, 317\u2013331 (1997)","journal-title":"J. Comput. System Sci."},{"key":"3_CR3","doi-asserted-by":"crossref","unstructured":"Bhattacharyya, A., Grigorescu, E., Jung, K., Raskhodnikova, S., Woodruff, D.P.: Transitive-Closure Spanners, ArXiv e-prints (2008)","DOI":"10.1137\/1.9781611973068.101"},{"key":"3_CR4","unstructured":"Breslau, L., Diakonikolas, I., Duffield, N., Gu, Y., Hajiaghayi, M., Johnson, D., Karloff, H., Resende, M., Sen, S.: Optimal Node Placement For Path-Disjoint Network Monitoring (manuscript) (2008)"},{"key":"3_CR5","unstructured":"Chen, N.: On the approximability of influence in social networks. In: SODA, pp. 1029\u20131037 (2008)"},{"key":"3_CR6","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1007\/s00224-006-1266-2","volume":"41","author":"M. Elkin","year":"2007","unstructured":"Elkin, M., Peleg, D.: The hardness of approximating spanner problems. Theory Comput. Syst.\u00a041, 691\u2013729 (2007)","journal-title":"Theory Comput. Syst."},{"key":"3_CR7","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1007\/s004530010050","volume":"29","author":"U. Feige","year":"2001","unstructured":"Feige, U., Kortsarz, G., Peleg, D.: The dense k-subgraph problem. Algorithmica\u00a029, 410\u2013421 (2001)","journal-title":"Algorithmica"},{"key":"3_CR8","doi-asserted-by":"crossref","unstructured":"Feldman, M., Kortsarz, G., Nutov, Z.: Improved approximation for the directed steiner forest problem. In: SODA 2009, pp. 922\u2013931 (2009)","DOI":"10.1137\/1.9781611973068.100"},{"key":"3_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1007\/978-3-540-74208-1_10","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"A. Gupta","year":"2007","unstructured":"Gupta, A., Hajiaghayi, M.T., Kumar, A.: Stochastic steiner tree with non-uniform inflation. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) RANDOM 2007 and APPROX 2007. LNCS, vol.\u00a04627, pp. 134\u2013148. Springer, Heidelberg (2007)"},{"key":"3_CR10","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/s10107-006-0057-5","volume":"110","author":"M.T. Hajiaghayi","year":"2007","unstructured":"Hajiaghayi, M.T., Kortsarz, G., Mirrokni, V.S., Nutov, Z.: Power optimization for connectivity problems. Math. Program.\u00a0110, 195\u2013208 (2007)","journal-title":"Math. Program."},{"key":"3_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/11590156_13","volume-title":"FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science","author":"R. Hassin","year":"2005","unstructured":"Hassin, R., Segev, D.: The set cover with pairs problem. In: Sarukkai, S., Sen, S. (eds.) FSTTCS 2005. LNCS, vol.\u00a03821, pp. 164\u2013176. Springer, Heidelberg (2005)"},{"volume-title":"Approximation algorithms for NP-hard problems","year":"1997","key":"3_CR12","unstructured":"Hochbaum, D.S. (ed.): Approximation algorithms for NP-hard problems. PWS Publishing Co., Boston (1997); see the section written by Arora and Lund"},{"key":"3_CR13","doi-asserted-by":"publisher","first-page":"1025","DOI":"10.1137\/S0097539705447037","volume":"36","author":"S. Khot","year":"2006","unstructured":"Khot, S.: Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique. SIAM J. Comput.\u00a036, 1025\u20131071 (2006)","journal-title":"SIAM J. Comput."},{"key":"3_CR14","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1007\/s00453-001-0021-y","volume":"30","author":"G. Kortsarz","year":"2001","unstructured":"Kortsarz, G.: On the hardness of approximating spanners. Algorithmica\u00a030, 432\u2013450 (2001)","journal-title":"Algorithmica"},{"key":"3_CR15","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1137\/S0097539702416736","volume":"33","author":"G. Kortsarz","year":"2004","unstructured":"Kortsarz, G., Krauthgamer, R., Lee, J.R.: Hardness of approximation for vertex-connectivity network design problems. SIAM Journal on Computing\u00a033, 185\u2013199 (2004)","journal-title":"SIAM Journal on Computing"},{"key":"3_CR16","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.jda.2006.03.008","volume":"5","author":"D. Peleg","year":"2007","unstructured":"Peleg, D.: Approximation algorithms for the $\\text{Label-Cover}\\sb {\\rm MAX}$ and Red-Blue Set Cover problems. J. Discrete Algorithms\u00a05, 55\u201364 (2007)","journal-title":"J. Discrete Algorithms"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04128-0_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T11:21:58Z","timestamp":1558524118000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04128-0_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642041273","9783642041280"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04128-0_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}