{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T04:28:54Z","timestamp":1764131334546},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2011,2,3]],"date-time":"2011-02-03T00:00:00Z","timestamp":1296691200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,9]]},"DOI":"10.1007\/s00453-010-9464-3","type":"journal-article","created":{"date-parts":[[2011,2,2]],"date-time":"2011-02-02T16:07:50Z","timestamp":1296662870000},"page":"190-206","source":"Crossref","is-referenced-by-count":12,"title":["Improved Approximation Algorithms for Label Cover Problems"],"prefix":"10.1007","volume":"61","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","published-online":{"date-parts":[[2011,2,3]]},"reference":[{"key":"9464_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-540-74208-1_1","volume-title":"The 9th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX)","author":"A. Aazami","year":"2007","unstructured":"Aazami, A., Stilp, M.D.: Approximation algorithms and hardness for domination with propagation. In: The 9th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), pp. 1\u201315 (2007)"},{"key":"9464_CR2","doi-asserted-by":"crossref","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. Syst. Sci. 54, 317\u2013331 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"9464_CR3","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/1806689.1806719","volume-title":"Proceedings of the Forty-Second Annual ACM Symposium on Theory of Computing (STOC)","author":"A. Bhaskara","year":"2010","unstructured":"Bhaskara, A., Charikar, M., Chlamtac, E., Feige, U., Vijayaraghavan, A.: Detecting high log-densities\u2013an O(n 1\/4) approximation for densest k-subgraph. In: Proceedings of the Forty-Second Annual ACM Symposium on Theory of Computing (STOC), pp.\u00a0201\u2013210. ACM, New York (2010)"},{"key":"9464_CR4","doi-asserted-by":"crossref","first-page":"932","DOI":"10.1137\/1.9781611973068.101","volume-title":"SODA \u201909, 20th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"A. Bhattacharyya","year":"2009","unstructured":"Bhattacharyya, A., Grigorescu, E., Jung, K., Raskhodnikova, S., Woodruff, D.P.: Transitive-closure spanners. In: SODA \u201909, 20th Annual ACM-SIAM Symposium on Discrete Algorithms, San\u00a0Francisco, pp.\u00a0932\u2013941 (2009)"},{"key":"9464_CR5","first-page":"60","volume-title":"2011 ALENEX proceedings","author":"L. Breslau","year":"2011","unstructured":"Breslau, L., Diakonikolas, I., Duffield, N., Gu, Y., Hajiaghayi, M., Johnson, D., Karloff, H., Resende, M.G.C., Sen, S.: Disjoint-path facility location: theory and practice. In: 2011 ALENEX proceedings, San Francisco, January 22, pp.\u00a060\u201374. SIAM, Philadelphia (2011)"},{"key":"9464_CR6","first-page":"1029","volume-title":"Proceedings of the Nineteenth Annual ACM-SIAM Symposium On Discrete Algorithms (SODA)","author":"N. Chen","year":"2008","unstructured":"Chen, N.: On the approximability of influence in social networks. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium On Discrete Algorithms (SODA), pp. 1029\u20131037. Society for Industrial and Applied Mathematics, Philadelphia (2008)"},{"key":"9464_CR7","doi-asserted-by":"crossref","first-page":"750","DOI":"10.1145\/301250.301447","volume-title":"Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing (STOC)","author":"Y. Dodis","year":"1999","unstructured":"Dodis, Y., Khanna, S.: Design networks with bounded pairwise distance. In: Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing (STOC), pp. 750\u2013759. ACM, New York (1999)"},{"key":"9464_CR8","doi-asserted-by":"crossref","first-page":"636","DOI":"10.1007\/3-540-45022-X_54","volume-title":"Proceedings of the 27th International Colloquium on Automata, Languages and Programming (ICALP)","author":"M. Elkin","year":"2000","unstructured":"Elkin, M., Peleg, D.: Strong inapproximability of the basic k-spanner problem. In: Proceedings of the 27th International Colloquium on Automata, Languages and Programming (ICALP), pp. 636\u2013647. Springer, London (2000)"},{"key":"9464_CR9","doi-asserted-by":"crossref","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. 41, 691\u2013729 (2007)","journal-title":"Theory Comput. Syst."},{"key":"9464_CR10","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1145\/1077464.1077470","volume":"1","author":"G. Even","year":"2005","unstructured":"Even, G., Kortsarz, G., Slany, W.: On network design problems: fixed cost flows and the covering Steiner problem. ACM Trans. Algorithms 1, 74\u2013101 (2005)","journal-title":"ACM Trans. Algorithms"},{"key":"9464_CR11","volume-title":"Proceedings of the 20th Annual ACM-SIAM Symposium On Discrete Algorithms (SODA)","author":"M. Feldman","year":"2009","unstructured":"Feldman, M., Kortsarz, G., Nutov, Z.: Improved approximation for the directed Steiner forest problem. In: Proceedings of the 20th Annual ACM-SIAM Symposium On Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, Philadelphia (2009)"},{"key":"9464_CR12","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1007\/978-3-540-74208-1_10","volume-title":"the 9th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX)","author":"A. Gupta","year":"2007","unstructured":"Gupta, A., Hajiaghayi, M., Kumar, A.: Stochastic Steiner tree with nonuniform inflation. In: the 9th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), pp. 134\u2013148 (2007)"},{"key":"9464_CR13","doi-asserted-by":"crossref","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. 110, 195\u2013208 (2007)","journal-title":"Math. Program."},{"key":"9464_CR14","series-title":"Lecture Notes in Comput. Sci.","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1007\/11590156_13","volume-title":"Foundations of Software Technology and Theoretical Computer Science (FSTTCS)","author":"R. Hassin","year":"2005","unstructured":"Hassin, R., Segev, D.: The set cover with pairs problem. In: Foundations of Software Technology and Theoretical Computer Science (FSTTCS). Lecture Notes in Comput. Sci., vol. 3821, pp. 164\u2013176. Springer, Berlin (2005)"},{"key":"9464_CR15","volume-title":"Approximation Algorithms for NP-hard Problems","year":"1997","unstructured":"Hochbaum, D.S. (ed.): Approximation Algorithms for NP-hard Problems. PWS Publishing, Boston (1997). See the section written by Arora and Lund"},{"key":"9464_CR16","doi-asserted-by":"crossref","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. 36, 1025\u20131071 (2006)","journal-title":"SIAM J. Comput."},{"key":"9464_CR17","doi-asserted-by":"crossref","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 30, 432\u2013450 (2001)","journal-title":"Algorithmica"},{"key":"9464_CR18","doi-asserted-by":"crossref","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 J. Comput. 33, 185\u2013199 (2004)","journal-title":"SIAM J. Comput."},{"key":"9464_CR19","doi-asserted-by":"crossref","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 label\u2014covermax and red-blue set cover problems. J.\u00a0Discrete Algorithms 5, 55\u201364 (2007)","journal-title":"J.\u00a0Discrete Algorithms"},{"key":"9464_CR20","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/s10626-006-6187-3","volume":"16","author":"K.R. Rohloff","year":"2006","unstructured":"Rohloff, K.R., Khuller, S., Kortsarz, G.: Approximating the minimal sensor selection for supervisory control. Discrete Event Dyn. Syst. 16, 143\u2013170 (2006)","journal-title":"Discrete Event Dyn. Syst."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9464-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9464-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9464-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,18]],"date-time":"2021-11-18T12:16:39Z","timestamp":1637237799000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9464-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,2,3]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,9]]}},"alternative-id":["9464"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9464-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,2,3]]}}}