liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Tight Approximability Results for the Maximum Solution Equation Problem over Abelian Groups
Linköping University, Department of Computer and Information Science.
2005 (English)Student thesis
Abstract [en]

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.

Place, publisher, year, edition, pages
Institutionen för datavetenskap , 2005. , 68 p.
Keyword [en]
systems of equations, finite groups, NP-hardness, approximation
National Category
Computer Science
Identifiers
URN: urn:nbn:se:liu:diva-3240ISRN: LITH-IDA-EX--05/049--SEOAI: oai:DiVA.org:liu-3240DiVA: diva2:20357
Uppsok
teknik
Supervisors
Examiners
Available from: 2005-09-08 Created: 2005-09-08

Open Access in DiVA

fulltext(464 kB)468 downloads
File information
File name FULLTEXT01.pdfFile size 464 kBChecksum MD5
693fc089c56ea3e0bd297fa7272fbf48059107be67570ed1bcb7e34eae9519ac36602007
Type fulltextMimetype application/pdf

By organisation
Department of Computer and Information Science
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 468 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 283 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf