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 Zp
Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
2005 (English)In: Mathematical Foundations of Computer Science 2005: 30th International Symposium, MFCS 2005, Gdansk, Poland, August 29–September 2, 2005. Proceedings / [ed] Joanna Je¸drzejowicz and Andrzej Szepietowski, Springer Berlin/Heidelberg, 2005, , p. 628-639p. 628-639Chapter in book (Refereed)
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 groups of the form Zp, where p is prime. We also prove that the weighted and unweighted versions of this problem have equal approximability thresholds. Furthermore, we show that the problem is equally hard to solve 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. All of our results also hold for a 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
Springer Berlin/Heidelberg, 2005. , p. 628-639p. 628-639
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 3618
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:liu:diva-31026DOI: 10.1007/11549345_54Local ID: 16729ISBN: 978-3-540-28702-5 (print)ISBN: 3-540-28702-7 (print)OAI: oai:DiVA.org:liu-31026DiVA, id: diva2:251849
Available from: 2009-10-09 Created: 2009-10-09 Last updated: 2018-01-26Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textfind book at a swedish library/hitta boken i ett svenskt biblioteklink

Authority records BETA

Kuivinen, Fredrik

Search in DiVA

By author/editor
Kuivinen, Fredrik
By organisation
TCSLAB - Theoretical Computer Science LaboratoryThe Institute of Technology
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 25 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