Det linjära komplementaritetsproblemet är ett kontinuerligt optimeringsproblem som generaliserar konvex quadratic programmering, Nash equilibria av bimatrix spel och flera sådana problem. Detta papper presenterar en kontinuerlig optimering formulering för viktat oberoende nummer av en graf genom att karakterisera det som den maximala viktade l1 norm över lösningen uppsättningen av ett linjärt komplementaritetsproblem (LCP). Minsta l1 norm av lösningar av denna LCP är en lägre gräns på den oberoende dominans nummer av grafen. Till skillnad från den maximala l1-normen är denna nedre gräns i allmänhet svag, men vi visar att den är stram om grafen är en skog. Med hjälp av metoder från teorin om LCPs, får vi några grafteoretiska resultat. I synnerhet ger vi en starkare variant av Lovász theta i en graf. Vi tillhandahåller sedan tillräckliga villkor för att en graf ska vara väl täckt, dvs. att alla maximala oberoende uppsättningar också ska vara maximala. Detta villkor är också visat sig vara nödvändigt för vältäckt om grafen är en skog. Slutligen visar minskningen av det maximala oberoende problemet till ett linjärt program med (linjära) komplementaritetsbegränsningar (LPCC) att LPCC är svåra att uppskatta.
Resultaten i REF visar att det är svårt att hitta ungefärliga lösningar på en LPCC.
A linear complementarity based characterization of the weighted independence number and the independent domination number in graphs
{'venue': 'Discrete Applied Mathematics, Volume 244, 31 July 2018, Pages 155-169', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}