Loading…
The Linear Complementarity Problems with a Few Variables per Constraint
In this paper, we consider the sparse linear complementarity problem, denoted by k -LCP: the coefficient matrices are restricted to have at most k nonzero entries per row. It is known that the 1-LCP is solvable in linear time, and the 3-LCP is strongly NP-hard. We show that the 2-LCP is strongly NP-...
Saved in:
| Published in: | Mathematics of operations research 2015-11, Vol.40 (4), p.1015-1026 |
|---|---|
| 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-c534t-f02d9d0636fe0adbed18d8b20072e07e852ca72a8db3f917ece059358db698ce3 |
|---|---|
| cites | cdi_FETCH-LOGICAL-c534t-f02d9d0636fe0adbed18d8b20072e07e852ca72a8db3f917ece059358db698ce3 |
| container_end_page | 1026 |
| container_issue | 4 |
| container_start_page | 1015 |
| container_title | Mathematics of operations research |
| container_volume | 40 |
| creator | Sumita, Hanna Kakimura, Naonori Makino, Kazuhisa |
| description | In this paper, we consider the sparse linear complementarity problem, denoted by
k
-LCP: the coefficient matrices are restricted to have at most
k
nonzero entries per row. It is known that the 1-LCP is solvable in linear time, and the 3-LCP is strongly NP-hard. We show that the 2-LCP is strongly NP-hard, and it can be solved in polynomial time if it is sign-balanced, i.e., each row of the matrix has at most one positive and one negative entry. Our second result matches the currently best-known complexity bound for the corresponding sparse linear feasibility problem. In addition, we show that an integer variant of the sign-balanced 2-LCP is weakly NP-hard and pseudo-polynomially solvable, and the generalized 1-LCP is strongly NP-hard. |
| doi_str_mv | 10.1287/moor.2014.0708 |
| format | article |
| fullrecord | <record><control><sourceid>gale_infor</sourceid><recordid>TN_cdi_gale_infotracacademiconefile_A435717651</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><galeid>A435717651</galeid><jstor_id>24540990</jstor_id><sourcerecordid>A435717651</sourcerecordid><originalsourceid>FETCH-LOGICAL-c534t-f02d9d0636fe0adbed18d8b20072e07e852ca72a8db3f917ece059358db698ce3</originalsourceid><addsrcrecordid>eNqFkt9r2zAQx0VpoVm7170NDHsazOlJtiz7sYS2KwRa-mPsTcj2OVGIrUyn0PW_n0w2ukCgCCTu9Pme7k7H2CcOUy5KddE756cCeD4FBeURm3ApilTmih-zCWRFnqpC_jxlH4hWAFwqnk_YzdMSk7kd0Phk5vrNGnscgvE2vCb33tXRpuTFhmVikmt8SX7EKxO9lGxwVAwUvLFDOGcnnVkTfvx7nrHn66un2fd0fndzO7ucp43M8pB2INqqhSIrOgTT1tjysi1rAaAEgsJSisYoYcq2zrqKK2wQZJXJaBdV2WB2xr7s4m68-7VFCnrltn6IT2quKg4ZB6neqIVZo7ZD52KWTW-p0Zd5FiuPneCRSg9QCxzQm7UbsLPRvcdPD_Bxtdjb5qDg654gMgF_h4XZEunbx4d99tt_bL2l-CcUN7KLZaCd5FAujXdEHju98bY3_lVz0OM46HEc9DgOehyHKPi8E6woxIt_tMhlDlUFb80Y6_I9vRfvD8S7ve0</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>1791031057</pqid></control><display><type>article</type><title>The Linear Complementarity Problems with a Few Variables per Constraint</title><source>JSTOR</source><source>Business Source Ultimate (EBSCOHost)</source><creator>Sumita, Hanna ; Kakimura, Naonori ; Makino, Kazuhisa</creator><creatorcontrib>Sumita, Hanna ; Kakimura, Naonori ; Makino, Kazuhisa</creatorcontrib><description>In this paper, we consider the sparse linear complementarity problem, denoted by
k
-LCP: the coefficient matrices are restricted to have at most
k
nonzero entries per row. It is known that the 1-LCP is solvable in linear time, and the 3-LCP is strongly NP-hard. We show that the 2-LCP is strongly NP-hard, and it can be solved in polynomial time if it is sign-balanced, i.e., each row of the matrix has at most one positive and one negative entry. Our second result matches the currently best-known complexity bound for the corresponding sparse linear feasibility problem. In addition, we show that an integer variant of the sign-balanced 2-LCP is weakly NP-hard and pseudo-polynomially solvable, and the generalized 1-LCP is strongly NP-hard.</description><identifier>ISSN: 0364-765X</identifier><identifier>EISSN: 1526-5471</identifier><identifier>DOI: 10.1287/moor.2014.0708</identifier><identifier>CODEN: MOREDQ</identifier><language>eng</language><publisher>Linthicum: INFORMS</publisher><subject>Analysis ; combinatorial algorithm ; Linear complementarity problem ; Linear programming ; Mathematical problems ; Matrix ; NP-hardness ; polynomial solvability ; Polynomials ; Studies ; two-variable constraints</subject><ispartof>Mathematics of operations research, 2015-11, Vol.40 (4), p.1015-1026</ispartof><rights>Copyright 2015 Institute for Operations Research and the Management Sciences</rights><rights>COPYRIGHT 2015 Institute for Operations Research and the Management Sciences</rights><rights>Copyright Institute for Operations Research and the Management Sciences Nov 2015</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c534t-f02d9d0636fe0adbed18d8b20072e07e852ca72a8db3f917ece059358db698ce3</citedby><cites>FETCH-LOGICAL-c534t-f02d9d0636fe0adbed18d8b20072e07e852ca72a8db3f917ece059358db698ce3</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.jstor.org/stable/pdf/24540990$$EPDF$$P50$$Gjstor$$H</linktopdf><linktohtml>$$Uhttps://www.jstor.org/stable/24540990$$EHTML$$P50$$Gjstor$$H</linktohtml><link.rule.ids>314,776,780,27901,27902,58213,58446</link.rule.ids></links><search><creatorcontrib>Sumita, Hanna</creatorcontrib><creatorcontrib>Kakimura, Naonori</creatorcontrib><creatorcontrib>Makino, Kazuhisa</creatorcontrib><title>The Linear Complementarity Problems with a Few Variables per Constraint</title><title>Mathematics of operations research</title><description>In this paper, we consider the sparse linear complementarity problem, denoted by
k
-LCP: the coefficient matrices are restricted to have at most
k
nonzero entries per row. It is known that the 1-LCP is solvable in linear time, and the 3-LCP is strongly NP-hard. We show that the 2-LCP is strongly NP-hard, and it can be solved in polynomial time if it is sign-balanced, i.e., each row of the matrix has at most one positive and one negative entry. Our second result matches the currently best-known complexity bound for the corresponding sparse linear feasibility problem. In addition, we show that an integer variant of the sign-balanced 2-LCP is weakly NP-hard and pseudo-polynomially solvable, and the generalized 1-LCP is strongly NP-hard.</description><subject>Analysis</subject><subject>combinatorial algorithm</subject><subject>Linear complementarity problem</subject><subject>Linear programming</subject><subject>Mathematical problems</subject><subject>Matrix</subject><subject>NP-hardness</subject><subject>polynomial solvability</subject><subject>Polynomials</subject><subject>Studies</subject><subject>two-variable constraints</subject><issn>0364-765X</issn><issn>1526-5471</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2015</creationdate><recordtype>article</recordtype><recordid>eNqFkt9r2zAQx0VpoVm7170NDHsazOlJtiz7sYS2KwRa-mPsTcj2OVGIrUyn0PW_n0w2ukCgCCTu9Pme7k7H2CcOUy5KddE756cCeD4FBeURm3ApilTmih-zCWRFnqpC_jxlH4hWAFwqnk_YzdMSk7kd0Phk5vrNGnscgvE2vCb33tXRpuTFhmVikmt8SX7EKxO9lGxwVAwUvLFDOGcnnVkTfvx7nrHn66un2fd0fndzO7ucp43M8pB2INqqhSIrOgTT1tjysi1rAaAEgsJSisYoYcq2zrqKK2wQZJXJaBdV2WB2xr7s4m68-7VFCnrltn6IT2quKg4ZB6neqIVZo7ZD52KWTW-p0Zd5FiuPneCRSg9QCxzQm7UbsLPRvcdPD_Bxtdjb5qDg654gMgF_h4XZEunbx4d99tt_bL2l-CcUN7KLZaCd5FAujXdEHju98bY3_lVz0OM46HEc9DgOehyHKPi8E6woxIt_tMhlDlUFb80Y6_I9vRfvD8S7ve0</recordid><startdate>20151101</startdate><enddate>20151101</enddate><creator>Sumita, Hanna</creator><creator>Kakimura, Naonori</creator><creator>Makino, Kazuhisa</creator><general>INFORMS</general><general>Institute for Operations Research and the Management Sciences</general><scope>AAYXX</scope><scope>CITATION</scope><scope>N95</scope><scope>XI7</scope><scope>ISR</scope><scope>JQ2</scope></search><sort><creationdate>20151101</creationdate><title>The Linear Complementarity Problems with a Few Variables per Constraint</title><author>Sumita, Hanna ; Kakimura, Naonori ; Makino, Kazuhisa</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c534t-f02d9d0636fe0adbed18d8b20072e07e852ca72a8db3f917ece059358db698ce3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2015</creationdate><topic>Analysis</topic><topic>combinatorial algorithm</topic><topic>Linear complementarity problem</topic><topic>Linear programming</topic><topic>Mathematical problems</topic><topic>Matrix</topic><topic>NP-hardness</topic><topic>polynomial solvability</topic><topic>Polynomials</topic><topic>Studies</topic><topic>two-variable constraints</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Sumita, Hanna</creatorcontrib><creatorcontrib>Kakimura, Naonori</creatorcontrib><creatorcontrib>Makino, Kazuhisa</creatorcontrib><collection>CrossRef</collection><collection>Gale Business Insights</collection><collection>Business Insights: Essentials</collection><collection>Gale In Context: Science</collection><collection>ProQuest Computer Science Collection</collection><jtitle>Mathematics of operations research</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Sumita, Hanna</au><au>Kakimura, Naonori</au><au>Makino, Kazuhisa</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>The Linear Complementarity Problems with a Few Variables per Constraint</atitle><jtitle>Mathematics of operations research</jtitle><date>2015-11-01</date><risdate>2015</risdate><volume>40</volume><issue>4</issue><spage>1015</spage><epage>1026</epage><pages>1015-1026</pages><issn>0364-765X</issn><eissn>1526-5471</eissn><coden>MOREDQ</coden><abstract>In this paper, we consider the sparse linear complementarity problem, denoted by
k
-LCP: the coefficient matrices are restricted to have at most
k
nonzero entries per row. It is known that the 1-LCP is solvable in linear time, and the 3-LCP is strongly NP-hard. We show that the 2-LCP is strongly NP-hard, and it can be solved in polynomial time if it is sign-balanced, i.e., each row of the matrix has at most one positive and one negative entry. Our second result matches the currently best-known complexity bound for the corresponding sparse linear feasibility problem. In addition, we show that an integer variant of the sign-balanced 2-LCP is weakly NP-hard and pseudo-polynomially solvable, and the generalized 1-LCP is strongly NP-hard.</abstract><cop>Linthicum</cop><pub>INFORMS</pub><doi>10.1287/moor.2014.0708</doi><tpages>12</tpages></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 0364-765X |
| ispartof | Mathematics of operations research, 2015-11, Vol.40 (4), p.1015-1026 |
| issn | 0364-765X 1526-5471 |
| language | eng |
| recordid | cdi_gale_infotracacademiconefile_A435717651 |
| source | JSTOR; Business Source Ultimate (EBSCOHost) |
| subjects | Analysis combinatorial algorithm Linear complementarity problem Linear programming Mathematical problems Matrix NP-hardness polynomial solvability Polynomials Studies two-variable constraints |
| title | The Linear Complementarity Problems with a Few Variables per Constraint |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-29T11%3A41%3A20IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-gale_infor&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=The%20Linear%20Complementarity%20Problems%20with%20a%20Few%20Variables%20per%20Constraint&rft.jtitle=Mathematics%20of%20operations%20research&rft.au=Sumita,%20Hanna&rft.date=2015-11-01&rft.volume=40&rft.issue=4&rft.spage=1015&rft.epage=1026&rft.pages=1015-1026&rft.issn=0364-765X&rft.eissn=1526-5471&rft.coden=MOREDQ&rft_id=info:doi/10.1287/moor.2014.0708&rft_dat=%3Cgale_infor%3EA435717651%3C/gale_infor%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c534t-f02d9d0636fe0adbed18d8b20072e07e852ca72a8db3f917ece059358db698ce3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=1791031057&rft_id=info:pmid/&rft_galeid=A435717651&rft_jstor_id=24540990&rfr_iscdi=true |