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 clausal constraints
Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
2010 (English)In: Theory of Computing Systems, ISSN 1432-4350, E-ISSN 1433-0490, Vol. 46, no 2, 370-395 p.Article in journal (Refereed) Published
Abstract [en]

We study a family of problems, called Maximum Solution (Max Sol), where the objective is to maximise a linear goal function over the feasible integer assignments to a set of variables subject to a set of constraints. When the domain is Boolean (i.e. restricted to {0,1}), the maximum solution problem is identical to the well-studied Max Ones problem, and the complexity and approximability is completely understood for all restrictions on the underlying constraints. We continue this line of research by considering the Max Sol problem for relations defined by regular signed logic over finite subsets of the natural numbers; the complexity of the corresponding decision problem has recently been classified by Creignou et al. (Theory Comput. Syst. 42(2):239–255, 2008). We give sufficient conditions for when such problems are polynomial-time solvable and we prove that they are APX-hard otherwise. Similar dichotomies are also obtained for variants of the Max Sol problem.

Place, publisher, year, edition, pages
2010. Vol. 46, no 2, 370-395 p.
National Category
Computer Science
Identifiers
URN: urn:nbn:se:liu:diva-44302DOI: 10.1007/s00224-008-9145-7Local ID: 76207OAI: oai:DiVA.org:liu-44302DiVA: diva2:265164
Available from: 2009-10-10 Created: 2009-10-10 Last updated: 2017-12-13

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Jonsson, PeterNordh, Gustav

Search in DiVA

By author/editor
Jonsson, PeterNordh, Gustav
By organisation
TCSLAB - Theoretical Computer Science LaboratoryThe Institute of Technology
In the same journal
Theory of Computing Systems
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

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