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
Max ones generalized to larger domains
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. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
LIX, École Polytechnique, 91128 Palaiseau, France.
2008 (English)In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 38, no 1, 329-365 p.Article in journal (Refereed) Published
Abstract [en]

We study a family of problems, called Maximum Solution, where the objective is to maximize 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 approximability is completely understood for all restrictions on the underlying constraints [S. Khanna, M. Sudan, L. Trevisan, and D. P. Williamson, SIAM J. Comput., 30 (2001), pp. 1863-1920]. We continue this line of research by considering domains containing more than two elements. We present two main results: a complete classification for the approximability of all maximal constraint languages over domains of cardinality at most 4, and a complete classification of the approximability of the problem when the set of allowed constraints contains all permutation constraints. Under the assumption that a conjecture due to Szczepara Minimal Clones Generated by Groupoids, Ph.D. thesis, Université de Móntreal, Montreal, QC, 1996] holds, we give a complete classification for all maximal constraint languages. These classes of languages are well studied in universal algebra and computer science, they have, for instance, been considered in connection with machine learning and constraint satisfaction. Our results are proved by using algebraic results from clone theory, and the results indicate that this approach is very powerful for classifying the approximability of certain optimization problems. © 2008 Society for Industrial and Applied Mathematics.

Place, publisher, year, edition, pages
2008. Vol. 38, no 1, 329-365 p.
Keyword [en]
Approximability, Combinatorial optimization, Constraint satisfaction, Universal algebra
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:liu:diva-48099DOI: 10.1137/060669231OAI: oai:DiVA.org:liu-48099DiVA: diva2:268995
Available from: 2009-10-11 Created: 2009-10-11 Last updated: 2017-12-13

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Jonsson, PeterKuivinen, Fredrik

Search in DiVA

By author/editor
Jonsson, PeterKuivinen, Fredrik
By organisation
The Institute of TechnologyTCSLAB - Theoretical Computer Science Laboratory
In the same journal
SIAM journal on computing (Print)
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

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