Hardness of Approximating Constraint Satisfaction Problems and Their Variants in Presence of Additional Structural Assumptions

QC 2023-05-08

Abstract

Denna avhandling undersöker hur approximerbarheten av vissa grundläggande datavetenskapliga problem på verkas av ytterligare krav på strukturen hos indata. De studerade problemen tillhör eller är nära relaterade till Constraint Satisfaction Problems (CSPs), som anses vara ett av de mest grundläggande problemen inom teoretisk datavetenskap.

Den första problemklassen som studeras i denna avhandling består av vissa Booleska CSPs med kardinalitetsbegränsningar. En kardinalitetsbegränsning för en instans av en Boolesk CSP begränsar tilldelningarna att ha ett visst antal variabler tilldelade till 1 och 0. Under antagandet att Unique Games Conjecture gäller, visar vi att Max-Cut med kardinalitetsbegränsningar är svårt att approximera inom cirka 0.858, och att Max-2-Sat med kardinalitetsbegränsningar är svårt att approximera inom cirka 0.929. Samma approximationsförhållande som för kardinalitetsbegränsad Max-2-Sat erhålls för kardinalitetsbegrän sade versionen av Vertex Cover-problemet, känd som Max-k-VC.

Vi undersöker också regelbundna begränsningsproblem där varje variabel i en instans har samma antal förekomster. Vi undersöker approximabiliteten för sådana problem och visar att för något CSP Λ så innebär existensen av en α-approximationsalgoritm för regelbundet Max-CSP Λ existensen av en (α − o(1))-approximationsalgoritm för viktade Max-CSP Λ där regelbundenheten för instanserna inte nödvändigtvis är uppfyllt. Vi ger också ett analogt resultat för Min-CSPs. Särskilt visar vi att om man inte är intresserad av termer med lägre ordning så kan undersökningen av approximabiliteten för CSPs utföras enbart på regelbundna instanser.

Vi undersöker även approximerbarheten hos Max-3-Lin problemen över icke-Abelska grupper med universell faktorgraf. Faktorgrafen för en instans med n variabler och m begränsningar är den bipartita grafen mellan [m] och [n] där kanterna kopplar begränsningar till variabler som de innehåller. Den universella faktorgrafen antar att en faktorgraf för en instans är fixerad för varje indatastorlek. Med utgångspunkt från tidigare arbeten visar vi optimal inapproximerbarhet av Max-3-Lin problemet över icke-Abelska grupper med universella faktorgrafer, både i fallet med perfekt och nästan perfekt fullständighet. Vi visar också att dessa svårighetsresultat gäller i fallet där linjära ekvationer i Max-3-Lin problemet är begränsade till formen x·y·z = g, där x, y, z är variablerna och g är ett gruppelement, till skillnad från tidigare arbeten där konstanter även har förekommit på vänster sida av ekvationerna.

Slutligen studerar vi approximabiliteten av Minimum Sum Vertex Cover-problemet, där vi får en graf som indata och målet är att hitta en ordning av hörn som minimerar den totala övertäcktningsiden för kanter. En kant täcks när en av dess ändpunkter besöks i en beställning, och omslaget tid för kanten är exakt den tidpunkt då ändpunkten besöks i ordningen.

I detta arbete ger vi det första explicita resultatet för svårighetsgraden av approximering och visar att Minimum Sum Vertex Cover inte kan approximeras nedanför 1.0748, under antagandet om Unique Games Conjecture. Vidare studerar vi Minimum Sum Certex Cover på regelbundna grafer och visar en inapproximationskvot på 1.0157. Genom att återbesöka en algoritm föreslagen av Feige, Lovász och Tetali, visar vi också approximerbarhet inom 1.225 för regelbundna grafer.

urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-326609