This thesis studies how the approximability of some fundamental computational problems is affected by some additional requirements on the structure of the inputs. The problems studied in this thesis belong or are closely related to constraint satisfaction problems (CSPs), which are considered to be one of the most fundamental problems in theoretical computer science.

The first class of problems studied in this thesis consists of some Boolean CSPs with cardinality constraints. A cardinality constraint for an instance of a Boolean CSP restricts assignments to have a certain number of variables assigned to 1 and 0. Assuming the Unique Games Conjecture, we show that Max-Cut with cardinality constraints is hard to approximate within approximately 0.858, and that Max-2-Sat with cardinality constraints is hard to approximate within approximately 0.929. The same inapproximability ratio as for cardinality constrained Max-2-Sat is obtained for the cardinality-constrained Vertex Cover problem, known as Max-k-VC.

We also examine regular constraint satisfaction problems where each variable in an instance has the same number of occurrences. We investigate approximability of such problems and show that for any CSP Λ, the existence of an α-approximation algorithm for regular Max-CSP Λ implies the existence of an (α − o(1))-approximation algorithm for weighted Max-CSP Λ for which the regularity of instances is not imposed. We also give an analogous result for Min-CSPs. In particular, if one is not interested in lower-order terms, we show that the study of the approximability of CSPs can be conducted solely on regular instances.

We also consider approximability of Max-3-Lin problems over non-Abelian groups in a universal factor graph setting. The factor graph of an instance with n variables and m constraints is the bipartite graph between [m] and [n], in which edges connect constraints with the variables they contain. The universal factor graph setting assumes that a factor graph for an instance is fixed for each input size. Building on the previous works, we show optimal inapproximability of Max-3-Lin problems over non-Abelian groups in the universal factor graph setting, both in the case of perfect and almost perfect completeness. We also show that these hardness results apply in the setting in which linear equations in the Max-3-Lin  problem are restricted  to the form x · y · z = g, where x, y, z are variables and $g$ is a group element, in contrast to previous works where constants have appeared on the left side of the equations as well.

Finally, we study the approximability of the Minimum Sum Vertex Cover problem, in which we are given a graph as an input and the goal is to find anordering of vertices that minimizes the total cover time of edges. An edge is covered when one of its endpoints is visited in an ordering, and the covertime for the edge is exactly the time that the endpoint is visited.

In this work, we give the first explicit hardness of approximation result and show that Minimum Sum Vertex Cover can not be approximated below 1.0748, assuming the Unique Games Conjecture. Furthermore, we study Minimum Sum Vertex Cover on regular graphs and demonstrate an inapproximability ratio of 1.0157. By revisiting an algorithm introduced by Feige, Lov\'{a}sz, and Tetali, we also show approximability within 1.225 for regular graphs.

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.