Loading…
On the hardness of approximating label-cover
The Label-Cover problem, defined by S. Arora, L. Babai, J. Stern, Z. Sweedyk [Proceedings of 34th IEEE Symposium on Foundations of Computer Science, 1993, pp. 724–733], serves as a starting point for numerous hardness of approximation reductions. It is one of six ‘canonical’ approximation problems i...
Saved in:
| Published in: | Information processing letters 2004-03, Vol.89 (5), p.247-254 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | English |
| Subjects: | |
| Citations: | Items that this one cites Items that cite this one |
| Online Access: | Get full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| cited_by | cdi_FETCH-LOGICAL-c418t-c5b3bd9f8e95207849f04b4613583e5242ebea8d5c5c19d05462b13d5cf003543 |
|---|---|
| cites | cdi_FETCH-LOGICAL-c418t-c5b3bd9f8e95207849f04b4613583e5242ebea8d5c5c19d05462b13d5cf003543 |
| container_end_page | 254 |
| container_issue | 5 |
| container_start_page | 247 |
| container_title | Information processing letters |
| container_volume | 89 |
| creator | Dinur, Irit Safra, Shmuel |
| description | The
Label-Cover problem, defined by S. Arora, L. Babai, J. Stern, Z. Sweedyk [Proceedings of 34th IEEE Symposium on Foundations of Computer Science, 1993, pp. 724–733], serves as a starting point for numerous hardness of approximation reductions. It is one of six ‘canonical’ approximation problems in the survey of Arora and Lund [Hardness of Approximations, in: Approximation Algorithms for NP-Hard Problems, PWS Publishing Company, 1996, Chapter 10]. In this paper we present a direct combinatorial reduction from low error-probability PCP [Proceedings of 31st ACM Symposium on Theory of Computing, 1999, pp. 29–40] to
Label-Cover showing it NP-hard to approximate to within 2
(log
n)
1−o(1)
. This improves upon the best previous hardness of approximation results known for this problem.
We also consider the
Minimum-Monotone-Satisfying-Assignment (MMSA) problem of finding a satisfying assignment to a monotone formula with the least number of 1's, introduced by M. Alekhnovich, S. Buss, S. Moran, T. Pitassi [Minimum propositional proof length is NP-hard to linearly approximate, 1998]. We define a hierarchy of approximation problems obtained by restricting the number of alternations of the monotone formula. This hierarchy turns out to be equivalent to an AND/OR scheduling hierarchy suggested by M.H. Goldwasser, R. Motwani [Lecture Notes in Comput. Sci., Vol. 1272, Springer-Verlag, 1997, pp. 307–320]. We show some hardness results for certain levels in this hierarchy, and place
Label-Cover between levels 3 and 4. This partially answers an open problem from M.H. Goldwasser, R. Motwani regarding the precise complexity of each level in the hierarchy, and the place of
Label-Cover in it. |
| doi_str_mv | 10.1016/j.ipl.2003.11.007 |
| format | article |
| fullrecord | <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_237282771</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S0020019003005167</els_id><sourcerecordid>547307981</sourcerecordid><originalsourceid>FETCH-LOGICAL-c418t-c5b3bd9f8e95207849f04b4613583e5242ebea8d5c5c19d05462b13d5cf003543</originalsourceid><addsrcrecordid>eNp9kM1Lw0AQxRdRsFb_AG9B8GbizH7kA08ifkGhFz0vm83EbohJ3U2L_vduacGbp2HgvTdvfoxdImQImN92mVv3GQcQGWIGUByxGZYFT3PE6pjNADikgBWcsrMQOgDIpShm7GY5JNOKkpXxzUAhJGObmPXaj9_u00xu-Eh6U1Of2nFL_pydtKYPdHGYc_b-9Pj28JIuls-vD_eL1Eosp9SqWtRN1ZZUKQ5FKasWZC1zFKoUpLjkVJMpG2WVxaoBJXNeo4h7G_srKebsap8be3xtKEy6Gzd-iCc1FwUveVFgFOFeZP0YgqdWr33s7H80gt4x0Z2OTPSOiUbUkUn0XB-CTbCmb70ZrAt_RiUrhSii7m6vo_jl1pHXwToaLDXOk510M7p_rvwC4YZ0Ng</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>237282771</pqid></control><display><type>article</type><title>On the hardness of approximating label-cover</title><source>ScienceDirect Journals</source><source>Elsevier</source><source>Backfile Package - Mathematics</source><creator>Dinur, Irit ; Safra, Shmuel</creator><creatorcontrib>Dinur, Irit ; Safra, Shmuel</creatorcontrib><description>The
Label-Cover problem, defined by S. Arora, L. Babai, J. Stern, Z. Sweedyk [Proceedings of 34th IEEE Symposium on Foundations of Computer Science, 1993, pp. 724–733], serves as a starting point for numerous hardness of approximation reductions. It is one of six ‘canonical’ approximation problems in the survey of Arora and Lund [Hardness of Approximations, in: Approximation Algorithms for NP-Hard Problems, PWS Publishing Company, 1996, Chapter 10]. In this paper we present a direct combinatorial reduction from low error-probability PCP [Proceedings of 31st ACM Symposium on Theory of Computing, 1999, pp. 29–40] to
Label-Cover showing it NP-hard to approximate to within 2
(log
n)
1−o(1)
. This improves upon the best previous hardness of approximation results known for this problem.
We also consider the
Minimum-Monotone-Satisfying-Assignment (MMSA) problem of finding a satisfying assignment to a monotone formula with the least number of 1's, introduced by M. Alekhnovich, S. Buss, S. Moran, T. Pitassi [Minimum propositional proof length is NP-hard to linearly approximate, 1998]. We define a hierarchy of approximation problems obtained by restricting the number of alternations of the monotone formula. This hierarchy turns out to be equivalent to an AND/OR scheduling hierarchy suggested by M.H. Goldwasser, R. Motwani [Lecture Notes in Comput. Sci., Vol. 1272, Springer-Verlag, 1997, pp. 307–320]. We show some hardness results for certain levels in this hierarchy, and place
Label-Cover between levels 3 and 4. This partially answers an open problem from M.H. Goldwasser, R. Motwani regarding the precise complexity of each level in the hierarchy, and the place of
Label-Cover in it.</description><identifier>ISSN: 0020-0190</identifier><identifier>EISSN: 1872-6119</identifier><identifier>DOI: 10.1016/j.ipl.2003.11.007</identifier><identifier>CODEN: IFPLAT</identifier><language>eng</language><publisher>Amsterdam: Elsevier B.V</publisher><subject>Applied sciences ; Approximation ; Computational complexity ; Computer science ; Computer science; control theory; systems ; Estimates ; Exact sciences and technology ; Hardness of approximation ; Label-cover ; Miscellaneous ; PCP ; Studies ; Theoretical computing</subject><ispartof>Information processing letters, 2004-03, Vol.89 (5), p.247-254</ispartof><rights>2003 Elsevier B.V.</rights><rights>2004 INIST-CNRS</rights><rights>Copyright Elsevier Sequoia S.A. Mar 16, 2004</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c418t-c5b3bd9f8e95207849f04b4613583e5242ebea8d5c5c19d05462b13d5cf003543</citedby><cites>FETCH-LOGICAL-c418t-c5b3bd9f8e95207849f04b4613583e5242ebea8d5c5c19d05462b13d5cf003543</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://www.sciencedirect.com/science/article/pii/S0020019003005167$$EHTML$$P50$$Gelsevier$$H</linktohtml><link.rule.ids>314,780,784,3429,3564,27924,27925,45972,46003</link.rule.ids><backlink>$$Uhttp://pascal-francis.inist.fr/vibad/index.php?action=getRecordDetail&idt=15495113$$DView record in Pascal Francis$$Hfree_for_read</backlink></links><search><creatorcontrib>Dinur, Irit</creatorcontrib><creatorcontrib>Safra, Shmuel</creatorcontrib><title>On the hardness of approximating label-cover</title><title>Information processing letters</title><description>The
Label-Cover problem, defined by S. Arora, L. Babai, J. Stern, Z. Sweedyk [Proceedings of 34th IEEE Symposium on Foundations of Computer Science, 1993, pp. 724–733], serves as a starting point for numerous hardness of approximation reductions. It is one of six ‘canonical’ approximation problems in the survey of Arora and Lund [Hardness of Approximations, in: Approximation Algorithms for NP-Hard Problems, PWS Publishing Company, 1996, Chapter 10]. In this paper we present a direct combinatorial reduction from low error-probability PCP [Proceedings of 31st ACM Symposium on Theory of Computing, 1999, pp. 29–40] to
Label-Cover showing it NP-hard to approximate to within 2
(log
n)
1−o(1)
. This improves upon the best previous hardness of approximation results known for this problem.
We also consider the
Minimum-Monotone-Satisfying-Assignment (MMSA) problem of finding a satisfying assignment to a monotone formula with the least number of 1's, introduced by M. Alekhnovich, S. Buss, S. Moran, T. Pitassi [Minimum propositional proof length is NP-hard to linearly approximate, 1998]. We define a hierarchy of approximation problems obtained by restricting the number of alternations of the monotone formula. This hierarchy turns out to be equivalent to an AND/OR scheduling hierarchy suggested by M.H. Goldwasser, R. Motwani [Lecture Notes in Comput. Sci., Vol. 1272, Springer-Verlag, 1997, pp. 307–320]. We show some hardness results for certain levels in this hierarchy, and place
Label-Cover between levels 3 and 4. This partially answers an open problem from M.H. Goldwasser, R. Motwani regarding the precise complexity of each level in the hierarchy, and the place of
Label-Cover in it.</description><subject>Applied sciences</subject><subject>Approximation</subject><subject>Computational complexity</subject><subject>Computer science</subject><subject>Computer science; control theory; systems</subject><subject>Estimates</subject><subject>Exact sciences and technology</subject><subject>Hardness of approximation</subject><subject>Label-cover</subject><subject>Miscellaneous</subject><subject>PCP</subject><subject>Studies</subject><subject>Theoretical computing</subject><issn>0020-0190</issn><issn>1872-6119</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2004</creationdate><recordtype>article</recordtype><recordid>eNp9kM1Lw0AQxRdRsFb_AG9B8GbizH7kA08ifkGhFz0vm83EbohJ3U2L_vduacGbp2HgvTdvfoxdImQImN92mVv3GQcQGWIGUByxGZYFT3PE6pjNADikgBWcsrMQOgDIpShm7GY5JNOKkpXxzUAhJGObmPXaj9_u00xu-Eh6U1Of2nFL_pydtKYPdHGYc_b-9Pj28JIuls-vD_eL1Eosp9SqWtRN1ZZUKQ5FKasWZC1zFKoUpLjkVJMpG2WVxaoBJXNeo4h7G_srKebsap8be3xtKEy6Gzd-iCc1FwUveVFgFOFeZP0YgqdWr33s7H80gt4x0Z2OTPSOiUbUkUn0XB-CTbCmb70ZrAt_RiUrhSii7m6vo_jl1pHXwToaLDXOk510M7p_rvwC4YZ0Ng</recordid><startdate>20040316</startdate><enddate>20040316</enddate><creator>Dinur, Irit</creator><creator>Safra, Shmuel</creator><general>Elsevier B.V</general><general>Elsevier Science</general><general>Elsevier Sequoia S.A</general><scope>IQODW</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>20040316</creationdate><title>On the hardness of approximating label-cover</title><author>Dinur, Irit ; Safra, Shmuel</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c418t-c5b3bd9f8e95207849f04b4613583e5242ebea8d5c5c19d05462b13d5cf003543</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2004</creationdate><topic>Applied sciences</topic><topic>Approximation</topic><topic>Computational complexity</topic><topic>Computer science</topic><topic>Computer science; control theory; systems</topic><topic>Estimates</topic><topic>Exact sciences and technology</topic><topic>Hardness of approximation</topic><topic>Label-cover</topic><topic>Miscellaneous</topic><topic>PCP</topic><topic>Studies</topic><topic>Theoretical computing</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Dinur, Irit</creatorcontrib><creatorcontrib>Safra, Shmuel</creatorcontrib><collection>Pascal-Francis</collection><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>Information processing letters</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Dinur, Irit</au><au>Safra, Shmuel</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>On the hardness of approximating label-cover</atitle><jtitle>Information processing letters</jtitle><date>2004-03-16</date><risdate>2004</risdate><volume>89</volume><issue>5</issue><spage>247</spage><epage>254</epage><pages>247-254</pages><issn>0020-0190</issn><eissn>1872-6119</eissn><coden>IFPLAT</coden><abstract>The
Label-Cover problem, defined by S. Arora, L. Babai, J. Stern, Z. Sweedyk [Proceedings of 34th IEEE Symposium on Foundations of Computer Science, 1993, pp. 724–733], serves as a starting point for numerous hardness of approximation reductions. It is one of six ‘canonical’ approximation problems in the survey of Arora and Lund [Hardness of Approximations, in: Approximation Algorithms for NP-Hard Problems, PWS Publishing Company, 1996, Chapter 10]. In this paper we present a direct combinatorial reduction from low error-probability PCP [Proceedings of 31st ACM Symposium on Theory of Computing, 1999, pp. 29–40] to
Label-Cover showing it NP-hard to approximate to within 2
(log
n)
1−o(1)
. This improves upon the best previous hardness of approximation results known for this problem.
We also consider the
Minimum-Monotone-Satisfying-Assignment (MMSA) problem of finding a satisfying assignment to a monotone formula with the least number of 1's, introduced by M. Alekhnovich, S. Buss, S. Moran, T. Pitassi [Minimum propositional proof length is NP-hard to linearly approximate, 1998]. We define a hierarchy of approximation problems obtained by restricting the number of alternations of the monotone formula. This hierarchy turns out to be equivalent to an AND/OR scheduling hierarchy suggested by M.H. Goldwasser, R. Motwani [Lecture Notes in Comput. Sci., Vol. 1272, Springer-Verlag, 1997, pp. 307–320]. We show some hardness results for certain levels in this hierarchy, and place
Label-Cover between levels 3 and 4. This partially answers an open problem from M.H. Goldwasser, R. Motwani regarding the precise complexity of each level in the hierarchy, and the place of
Label-Cover in it.</abstract><cop>Amsterdam</cop><pub>Elsevier B.V</pub><doi>10.1016/j.ipl.2003.11.007</doi><tpages>8</tpages></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 0020-0190 |
| ispartof | Information processing letters, 2004-03, Vol.89 (5), p.247-254 |
| issn | 0020-0190 1872-6119 |
| language | eng |
| recordid | cdi_proquest_journals_237282771 |
| source | ScienceDirect Journals; Elsevier; Backfile Package - Mathematics |
| subjects | Applied sciences Approximation Computational complexity Computer science Computer science control theory systems Estimates Exact sciences and technology Hardness of approximation Label-cover Miscellaneous PCP Studies Theoretical computing |
| title | On the hardness of approximating label-cover |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-07T20%3A43%3A55IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=On%20the%20hardness%20of%20approximating%20label-cover&rft.jtitle=Information%20processing%20letters&rft.au=Dinur,%20Irit&rft.date=2004-03-16&rft.volume=89&rft.issue=5&rft.spage=247&rft.epage=254&rft.pages=247-254&rft.issn=0020-0190&rft.eissn=1872-6119&rft.coden=IFPLAT&rft_id=info:doi/10.1016/j.ipl.2003.11.007&rft_dat=%3Cproquest_cross%3E547307981%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c418t-c5b3bd9f8e95207849f04b4613583e5242ebea8d5c5c19d05462b13d5cf003543%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=237282771&rft_id=info:pmid/&rfr_iscdi=true |