liu.seSearch for publications in DiVA
Change search
Link to record
Permanent link

Direct link
BETA
Thapper, Johan
Publications (10 of 16) Show all publications
Jonsson, P., Kuivinen, F. & Thapper, J. (2011). Min CSP on four elements: moving beyond submodularity. In: Jimmy Lee (Ed.), Proceedings of the 17th international conference on Principles and practice of constraint programming. Paper presented at 17th International Conference on Principles and Practice of Constraint Programming (CP'11) (pp. 438-453). Springer Berlin/Heidelberg
Open this publication in new window or tab >>Min CSP on four elements: moving beyond submodularity
2011 (English)In: Proceedings of the 17th international conference on Principles and practice of constraint programming / [ed] Jimmy Lee, Springer Berlin/Heidelberg, 2011, p. 438-453Conference paper, Published paper (Refereed)
Abstract [en]

We report new results on the complexity of the valued constraint satisfaction problem (VCSP). Under the unique games conjecture, the approximability of finite-valued VCSP is fairly well-understood. However, there is yet no characterisation of VCSPs that can be solved exactly in polynomial time. This is unsatisfactory, since such results are interesting from a combinatorial optimisation perspective; there are deep connections with, for instance, submodular and bisubmodular minimisation. We consider the Min and Max CSP problems (i.e. where the cost functions only attain values in {0,1}) over four-element domains and identify all tractable fragments. Similar classifications were previously known for two- and three-element domains. In the process, we introduce a new class of tractable VCSPs based on a generalisation of submodularity. We also extend and modify a graph-based technique by Kolmogorov and Živný (originally introduced by Takhanov) for efficiently obtaining hardness results in our setting. This allow us to prove the result without relying on computer-assisted case analyses (which is fairly common when studying VCSPs). The hardness results are further simplified by the introduction of powerful reduction techniques.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2011
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 6876
Keywords
Constraint satisfaction problems, combinatorial optimisation, computational complexity, submodularity, bisubmodularity
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-74501 (URN)10.1007/978-3-642-23786-7_34 (DOI)978-3-642-23785-0 (ISBN)
Conference
17th International Conference on Principles and Practice of Constraint Programming (CP'11)
Available from: 2012-01-30 Created: 2012-01-30 Last updated: 2018-01-12
Thapper, J. (2010). Aspects of a Constraint Optimisation Problem. (Doctoral dissertation). Linköping: Linköping University Electronic Press
Open this publication in new window or tab >>Aspects of a Constraint Optimisation Problem
2010 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

In this thesis we study a constraint optimisation problem called the maximum solution problem, henceforth referred to as Max Sol. It is defined as the problem of optimising a linear objective function over a constraint satisfaction problem (Csp) instance on a finite domain. Each variable in the instance is given a non-negative rational weight, and each domain element is also assigned a numerical value, for example taken from the natural numbers. From this point of view, the problem is seen to be a natural extension of integer linear programming over a bounded domain. We study both the time complexity of approximating Max Sol, and the time complexity of obtaining an optimal solution. In the latter case, we also construct some exponential-time algorithms.

The algebraic method is a powerful tool for studying Csp-related problems. It was introduced for the decision version of Csp, and has been extended to a number of other problems, including Max Sol. With this technique we establish approximability classifications for certain families of constraint languages, based on algebraic characterisations. We also show how the concept of a core for relational structures can be extended in order to determine when constant unary relations can be added to a constraint language, without changing the computational complexity of finding an optimal solution to Max Sol. Using this result we show that, in a specific sense, when studying the computational complexity of Max Sol, we only need to consider constraint languages with all constant unary relations included.

Some optimisation problems are known to be approximable within some constant ratio, but are not believed to be approximable within an arbitrarily small constant ratio. For such problems, it is of interest to find the best ratio within which the problem can be approximated, or at least give some bounds on this constant. We study this aspect of the (weighted) Max Csp problem for graphs. In this optimisation problem the number of satisfied constraints is supposed to be maximised. We introduce a method for studying approximation ratios which is based on a new parameter on the space of all graphs. Informally, we think of this parameter as an approximation distance; knowing the distance between two graphs, we can bound the approximation ratio of one of them, given a bound for the other. We further show how the basic idea can be implemented also for the Max Sol problem.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2010. p. 218
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1294
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-52103 (URN)978-91-7393-464-0 (ISBN)
Public defence
2010-02-05, Visionen, hus B, Campus Valla, Linköpings universitet, Linköping, 13:15 (English)
Opponent
Supervisors
Available from: 2009-12-21 Created: 2009-12-04 Last updated: 2009-12-21Bibliographically approved
Färnqvist, T., Jonsson, P. & Thapper, J. (2009). Approximability Distance in the Space of H-Colourability Problems. COMPUTER SCIENCE - THEORY AND APPLICATIONS, 5675, 92-104
Open this publication in new window or tab >>Approximability Distance in the Space of H-Colourability Problems
2009 (English)In: COMPUTER SCIENCE - THEORY AND APPLICATIONS, ISSN 0302-9743, Vol. 5675, p. 92-104Article in journal (Refereed) Published
Abstract [en]

A graph homomorphism is a vertex map which carries edges from a source graph to edges in a target graph. We Study the approximability properties of the Weigh feel Maximum H-Colourable Subgraph problem (MAX H-COL). The instances of this problem are edge-weighted graphs G and the objective is to find a subgraph of G that has maximal total edge weight, under the condition that the subgraph has a homomorphism to H note that for H = K-k this problem is equivalent to MAX k-CUT. To this end, we introduce a metric structure on the space of graphs which allows us to extend previously known approximability results to larger classes of graphs. Specifically, the approximation algorithms for MAX CUT by Goemans and Williamson and MAX k-CUT by Frieze and Jerrum can he used to yield non-trivial approximation results for MAX H-COL For a variety of graphs, we show near-optimality results under the Unique Games Conjecture. We also use our method for comparing the performance of Frieze andamp; Jerrums algorithm with Hastads approximation algorithm for general MAX 2-CSP. This comparison is, in most cases, favourable to Frieze andamp; Jerrum.

Keywords
optimisation, approximability, graph homomorphism, graph H-colouring, computational complexity
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-21521 (URN)10.1007/978-3-642-03351-3_11 (DOI)
Available from: 2009-10-02 Created: 2009-10-02 Last updated: 2017-02-23
Jonsson, P. & Thapper, J. (2009). Approximability of the Maximum Solution Problem for Certain Families of Algebras. In: Proc 4th International Computer Science Symposium in Russia: . Paper presented at CSR-2009 (pp. 215-226). Berlin / Heidelberg: Springer
Open this publication in new window or tab >>Approximability of the Maximum Solution Problem for Certain Families of Algebras
2009 (English)In: Proc 4th International Computer Science Symposium in Russia, Berlin / Heidelberg: Springer , 2009, p. 215-226Conference 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
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-52639 (URN)10.1007/978-3-642-03351-3_21 (DOI)978-3-642-03350-6 (ISBN)
Conference
CSR-2009
Available from: 2010-01-06 Created: 2010-01-06 Last updated: 2018-02-15
Engström, R., Färnqvist, T., Jonsson, P. & Thapper, J. (2009). Properties of an Approximability-related Parameter on Circular Complete Graphs. Electronic Notes in Discrete Mathematics, 35, 115-120
Open this publication in new window or tab >>Properties of an Approximability-related Parameter on Circular Complete Graphs
2009 (English)In: Electronic Notes in Discrete Mathematics, ISSN 1571-0653, E-ISSN 1571-0653, Vol. 35, p. 115-120Article in journal (Refereed) Published
Abstract [en]

The instances of the Weighted Maximum H-Colourable Subgraph problem (Max H-Col) are edge-weighted graphs G and the objective is to find a subgraph of G that has maximal total edge weight, under the condition that the subgraph has a homomorphism to H; note that for H=Kk this problem is equivalent to Max k-cut. Färnqvist et al. have introduced a parameter on the space of graphs that allows close study of the approximability properties of Max H-Col. Here, we investigate the properties of this parameter on circular complete graphs Kp/q, where 2p/q3. The results are extended to K4-minor-free graphs. We also consider connections with Šámal's work on fractional covering by cuts: we address, and decide, two conjectures concerning cubical chromatic numbers.

Place, publisher, year, edition, pages
Elsevier, 2009
Keywords
graph H-colouring; circular colouring; combinatorial optimisation; graph theory
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-52637 (URN)10.1016/j.endm.2009.11.020 (DOI)
Available from: 2010-01-06 Created: 2010-01-06 Last updated: 2017-12-12
Thapper, J. (2007). Combinatorial Considerations on Two Models from Statistical Mechanics. (Licentiate dissertation). Matematiska institutionen
Open this publication in new window or tab >>Combinatorial Considerations on Two Models from Statistical Mechanics
2007 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

Interactions between combinatorics and statistical mechanics have provided many fruitful insights in both fields. A compelling example is Kuperberg’s solution to the alternating sign matrix conjecture, and its following generalisations. In this thesis we investigate two models from statistical mechanics which have received attention in recent years.

The first is the fully packed loop model. A conjecture from 2001 by Razumov and Stroganov opened the field for a large ongoing investigation of the O(1) loop model and its connections to a refinement of the fully packed loop model. We apply a combinatorial bijection originally found by de Gier to an older conjecture made by Propp.

The second model is the hard particle model. Recent discoveries by Fendley et al. and results by Jonsson suggests that the hard square model with cylindrical boundary conditions possess some beautiful combinatorial properties. We apply both topological and purely combinatorial methods to related independence complexes to try and gain a better understanding of this model.

Place, publisher, year, edition, pages
Matematiska institutionen, 2007. p. 7
Series
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 1335
Keywords
fully packed loop model, rhombus tilings, hard particle model, independence complex, discrete morse theory
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:liu:diva-10141 (URN)LIU-TEK-LIC-2007:44 (Local ID)978-91-85895-44-1 (ISBN)LIU-TEK-LIC-2007:44 (Archive number)LIU-TEK-LIC-2007:44 (OAI)
Presentation
2007-11-16, 10:15 (English)
Opponent
Supervisors
Available from: 2007-10-29 Created: 2007-10-29 Last updated: 2010-01-12
Thapper, J. (2007). Refined Counting of Fully Packed Loop Configurations. Séminaire Lotharingien de Combinatoire, 56, 1-27
Open this publication in new window or tab >>Refined Counting of Fully Packed Loop Configurations
2007 (English)In: Séminaire Lotharingien de Combinatoire, ISSN 1286-4889, Vol. 56, p. 1-27Article in journal (Refereed) Published
Abstract [en]

We give a generalisation of a conjecture by Propp on a summation formula for fully packed loop configurations. The original conjecture states that the number of configurations in which each external edge is connected to its neighbour is equal to the total number of configurations of size one less. This conjecture was later generalised by Zuber to include more types of configurations. Our conjecture further refines the counting and provides a general framework for some other summation formulas observed by Zuber. It also implies similar summation formulas for half-turn symmetric configurations.

National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-12703 (URN)
Available from: 2007-10-29 Created: 2007-10-29
Jonsson, P., Nordh, G. & Thapper, J. (2007). The Maximum Solution Problem on Graphs. In: Proc MFCS-2007, LNCS 4708,2007 (pp. 228). Berlin: Springer
Open this publication in new window or tab >>The Maximum Solution Problem on Graphs
2007 (English)In: Proc MFCS-2007, LNCS 4708,2007, Berlin: Springer , 2007, p. 228-Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Berlin: Springer, 2007
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-40857 (URN)10.1007/978-3-540-74456-6_22 (DOI)54333 (Local ID)978-3-540-74455-9 (ISBN)54333 (Archive number)54333 (OAI)
Available from: 2009-10-10 Created: 2009-10-10 Last updated: 2018-01-13
Angelsmark, O. & Thapper, J. (2006). Algorithms for the maximum hamming distance problem. In: Boi V. Faltings, Adrian Petcu, François Fages and Francesca Rossi (Ed.), Recent Advances in Constraints: Joint ERCIM/CoLogNET International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 2005, Uppsala, Sweden, June 20-22, 2005, Revised Selected and Invited Papers (pp. 128-141). Springer Berlin/Heidelberg, 3419
Open this publication in new window or tab >>Algorithms for the maximum hamming distance problem
2006 (English)In: Recent Advances in Constraints: Joint ERCIM/CoLogNET International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 2005, Uppsala, Sweden, June 20-22, 2005, Revised Selected and Invited Papers / [ed] Boi V. Faltings, Adrian Petcu, François Fages and Francesca Rossi, Springer Berlin/Heidelberg, 2006, Vol. 3419, p. 128-141Chapter in book (Refereed)
Abstract [en]

This book constitutes the thoroughly refereed and extended post-proceedings of the Joint ERCIM/CoLogNet International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 2005, held in Uppsala, Sweden in June 2005.

Besides papers taken from the workshop, others are submitted in response to an open call for papers after the workshop.

The 12 revised full papers presented were carefully reviewed and selected for inclusion in the book. The papers are organized in topical sections on global constraints, search and heuristics, language and implementation issues, and modeling

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2006
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 3419
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-48209 (URN)10.1007/11402763_10 (DOI)3-540-25176-6 (ISBN)978-3-540-34215-1 (ISBN)
Available from: 2009-10-11 Created: 2009-10-11 Last updated: 2018-01-23Bibliographically approved
Angelsmark, O. & Thapper, J. (2006). Algorithms for the Maximum Hamming Distance Problem. In: Boi V. Faltings, Adrian Petcu, François Fages and Francesca Rossi (Ed.), Recent Advances in Constraints: Joint ERCIM/CoLogNet International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 2004, Lausanne, Switzerland, June 23-25, 2004, Revised Selected and Invited Papers (pp. 128-141). Springer Berlin/Heidelberg
Open this publication in new window or tab >>Algorithms for the Maximum Hamming Distance Problem
2006 (English)In: Recent Advances in Constraints: Joint ERCIM/CoLogNet International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 2004, Lausanne, Switzerland, June 23-25, 2004, Revised Selected and Invited Papers / [ed] Boi V. Faltings, Adrian Petcu, François Fages and Francesca Rossi, Springer Berlin/Heidelberg, 2006, p. 128-141Chapter in book (Refereed)
Abstract [en]

This book constitutes the thoroughly refereed and extended post-proceedings of the Joint ERCIM/CoLogNet International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 2005, held in Uppsala, Sweden in June 2005.

Besides papers taken from the workshop, others are submitted in response to an open call for papers after the workshop.

The 12 revised full papers presented were carefully reviewed and selected for inclusion in the book. The papers are organized in topical sections on global constraints, search and heuristics, language and implementation issues, and modeling.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2006
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 3419
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 3419
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-31032 (URN)10.1007/11402763_10 (DOI)16737 (Local ID)978-3-540-25176-7 (ISBN)978-3-540-32252-8 (ISBN)3-540-25176-6 (ISBN)16737 (Archive number)16737 (OAI)
Available from: 2009-10-09 Created: 2009-10-09 Last updated: 2018-02-09Bibliographically approved
Organisations

Search in DiVA

Show all publications