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
Approximability of the Maximum Solution Problem for Certain Families of Algebras
Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
2009 (English)In: Proc 4th International Computer Science Symposium in Russia, Berlin / Heidelberg: Springer , 2009, 215-226 p.Conference paper, Published paper (Refereed)
Abstract [en]

We study the approximability of the maximum solution problem. This problem is an optimisation variant of the constraint satisfaction problem and it captures a wide range of interesting problems in, for example, integer programming, equation solving, and graph theory. The approximability of this problem has previously been studied in the two-element case [Khanna et al, ‘The approximability of constraint satisfaction’, SIAM Journal on Computing 23(6), 2000] and in some algebraically motivated cases [Jonsson et al, ‘Max Ones generalized to larger domains’, SIAM Journal on Computing 38(1), 2008]. We continue this line of research by considering the approximability of Max Sol for different types of constraints. Our investigation combined with the older results strengthens the hypothesis that Max Sol exhibits a pentachotomy with respect to approximability.

Place, publisher, year, edition, pages
Berlin / Heidelberg: Springer , 2009. 215-226 p.
Series
Lecture Notes On Computer Science, ISSN 0302-9743 (Print) 1611-3349 (Online)
National Category
Computer Science
Identifiers
URN: urn:nbn:se:liu:diva-52639DOI: 10.1007/978-3-642-03351-3_21ISBN: 978-3-642-03350-6 (print)OAI: oai:DiVA.org:liu-52639DiVA: diva2:284375
Conference
CSR-2009
Available from: 2010-01-06 Created: 2010-01-06 Last updated: 2017-02-23

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Jonsson, PeterThapper, Johan

Search in DiVA

By author/editor
Jonsson, PeterThapper, Johan
By organisation
TCSLAB - Theoretical Computer Science LaboratoryThe Institute of Technology
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

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