Tight Approximability Results for the Maximum Solution Equation Problem over Abelian Groups

Autor:	Kuivinen, Fredrik
Jazyk:	angličtina
Rok vydání:	2005
Předmět:	systems of equations finite groups NP-hardness approximation Computer Sciences Datavetenskap (datalogi)
Druh dokumentu:	Text
Popis:	In the maximum solution equation problem a collection of equations are given over some algebraic structure. The objective is to find an assignment to the variables in the equations such that all equations are satisfied and the sum of the variables is maximised. We give tight approximability results for the maximum solution equation problem when the equations are given over finite abelian groups. We also prove that the weighted and unweighted versions of this problem have asymptotically equal approximability thresholds. Furthermore, we show that the problem is equally hard to solve as the general problem even if each equation is restricted to contain at most three variables and solvable in polynomial time if the equations are restricted to contain at most two variables each. All of our results also hold for the generalised version of maximum solution equation where the elements of the group are mapped arbitrarily to non-negative integers in the objective function.
Databáze:	Networked Digital Library of Theses & Dissertations
Externí odkaz:	http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-3240 Zobrazit plný text záznamu