liu.seSearch for publications in DiVA
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Approximability of the Maximum Solution Problem for Certain Families of Algebras
Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi. Linköpings universitet, Tekniska högskolan.
Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi. Linköpings universitet, Tekniska högskolan.
2009 (engelsk)Inngår i: Proc 4th International Computer Science Symposium in Russia, Berlin / Heidelberg: Springer , 2009, s. 215-226Konferansepaper, Publicerat paper (Fagfellevurdert)
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.

sted, utgiver, år, opplag, sider
Berlin / Heidelberg: Springer , 2009. s. 215-226
Serie
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349
HSV kategori
Identifikatorer
URN: urn:nbn:se:liu:diva-52639DOI: 10.1007/978-3-642-03351-3_21ISBN: 978-3-642-03350-6 (tryckt)OAI: oai:DiVA.org:liu-52639DiVA, id: diva2:284375
Konferanse
CSR-2009
Tilgjengelig fra: 2010-01-06 Laget: 2010-01-06 Sist oppdatert: 2018-02-15

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fulltekst

Personposter BETA

Jonsson, PeterThapper, Johan

Søk i DiVA

Av forfatter/redaktør
Jonsson, PeterThapper, Johan
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric

doi
isbn
urn-nbn
Totalt: 31 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf