liu.seSearch for publications in DiVA
Change search
Refine search result
1 - 16 of 16
CiteExportLink to result list
Permanent 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
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1.
    Angelsmark, Ola
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
    Jonsson, Peter
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
    Linusson, Svante
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Applied Mathematics.
    Thapper, Johan
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Applied Mathematics.
    Determining the Number of Solutions to Binary CSP Instances2002In: Principles and Practice of Constraint Programming, 8th International Conference CP-2002,2002, Heidelberg: Springer Verlag , 2002, p. 327-Conference paper (Refereed)
    Abstract [en]

    Counting the number of solutions to CSP instances has applications in several areas, ranging from statistical physics to artificial intelligence. We give an algorithm for counting the number of solutions to binary CSPs, which works by transforming the problem into a number of 2-SAT instances, where the total number of solutions to these instances is the same as those of the original problem. The algorithm consists of two main cases, depending on whether the domain size d is even, in which case the algorithm runs in O(1.3247^n*(d/2)^n) time, or odd, in which case it runs in O(1.3247^n*((d^2+d+2)/4)^(n/2)) if d=4*k+1, and O(1.3247^n*((d^2+d)/4)^(n/2)) if d=4*k+3. We also give an algorithm for counting the number of possible 3-colourings of a given graph, which runs in O(1.8171^n), an improvement over our general algorithm gained by using problem specific knowledge. 

  • 2.
    Angelsmark, Ola
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
    Thapper, Johan
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Applied Mathematics.
    A Microstructure Based Approach to Constraint Satisfaction Optimisation Problems2005In: The 18th International FLAIRS Conference,2005, Menlo Park, CA, USA: AAAI Press , 2005, p. 155-Conference paper (Refereed)
    Abstract [en]

    We study two constraint satisfaction optimisation problems: The Max Value problem for CSPs, which, somewhat simplified, aims at maximising the sum of the (weighted) variable values in the solution, and the Max Ind problem, where the goal is to find a satisfiable subinstance of the original instance containing as many variables as possible. Both problems are NP-hard to approximate within n^(1-e), e>0, where n is the number of variables in the problems, which implies that it is of interest to find exact algorithms. By exploiting properties of the microstructure, we construct algorithms for solving instances of these problems with small domain sizes, and then, using a probabilistic reasoning, we show how to get algorithms for more general versions of the problems. The resulting algorithms have running times of O((0.585d)^n) for Max Value (d,2)-CSP, and O((0.503d)^n) for MaxInd (d,2)-CSP. Both algorithms represent the best known theoretical bounds for their respective problem, and, more importantly, the methods used are applicable to a wide range of optimisation problems. 

  • 3.
    Angelsmark, Ola
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
    Thapper, Johan
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
    Algorithms for the maximum hamming distance problem2006In: 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

  • 4.
    Angelsmark, Ola
    et al.
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Thapper, Johan
    Linköping University, Department of Mathematics, Applied Mathematics. Linköping University, The Institute of Technology.
    Algorithms for the Maximum Hamming Distance Problem2006In: 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.

  • 5.
    Angelsmark, Ola
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
    Thapper, Johan
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Applied Mathematics.
    New Algorithms for the Maximum Hamming Distance Problem2004In: Joint Annual Workshop of ERCIMCoLogNet on Constraint Solving and Constraint Logic Programming,2004, 2004, p. 271-285Conference paper (Refereed)
  • 6.
    Angelsmark, Ola
    et al.
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Thapper, Johan
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Partitioning based algorithms for some colouring problems2006In: Recent Advances in Constraints / [ed] Brahim Hnich, Mats Carlsson, François Fages and Francesca Rossi, Springer Berlin/Heidelberg, 2006, Vol. 3978, p. 44-58Chapter 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.

  • 7.
    Engström, Robert
    et al.
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Färnqvist, Tommy
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Thapper, Johan
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Properties of an Approximability-related Parameter on Circular Complete Graphs2009In: Electronic Notes in Discrete Mathematics, ISSN 1571-0653, E-ISSN 1571-0653, Vol. 35, p. 115-120Article in journal (Refereed)
    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.

  • 8.
    Färnqvist, Tommy
    et al.
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Thapper, Johan
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Approximability Distance in the Space of H-Colourability Problems2009In: COMPUTER SCIENCE - THEORY AND APPLICATIONS, ISSN 0302-9743, Vol. 5675, p. 92-104Article in journal (Refereed)
    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.

  • 9.
    Jonsson, Peter
    et al.
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Kuivinen, Fredrik
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Thapper, Johan
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Min CSP on four elements: moving beyond submodularity2011In: Proceedings of the 17th international conference on Principles and practice of constraint programming / [ed] Jimmy Lee, Springer Berlin/Heidelberg, 2011, p. 438-453Conference 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.

  • 10.
    Jonsson, Peter
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
    Nordh, Gustav
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
    Thapper, Johan
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
    The Maximum Solution Problem on Graphs2007In: Proc MFCS-2007, LNCS 4708,2007, Berlin: Springer , 2007, p. 228-Conference paper (Refereed)
  • 11.
    Jonsson, Peter
    et al.
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Thapper, Johan
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Approximability of the Maximum Solution Problem for Certain Families of Algebras2009In: Proc 4th International Computer Science Symposium in Russia, Berlin / Heidelberg: Springer , 2009, p. 215-226Conference 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.

  • 12.
    Thapper, Johan
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Aspects of a Constraint Optimisation Problem2010Doctoral 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.

  • 13.
    Thapper, Johan
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Combinatorial Considerations on Two Models from Statistical Mechanics2007Licentiate 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.

    List of papers
    1. Refined Counting of Fully Packed Loop Configurations
    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
    2. Independence Complexes of Cylinders Constructed from Square and Hexagonal Grid Graphs
    Open this publication in new window or tab >>Independence Complexes of Cylinders Constructed from Square and Hexagonal Grid Graphs
    (English)Manuscript (Other academic)
    Abstract [en]

    In the paper [Fendley et al., J. Phys. A: Math. Gen., 38 (2005), pp. 315-322], Fendley, Schoutens and van Eerten studied the hard square model at negative activity. They found analytical and numerical evidence that the eigenvalues of the transfer matrix with periodic boundary were all roots of unity. They also conjectured that for an m × n square grid, with doubly periodic boundary, the partition function is equal to 1 when m and n are relatively prime. These conjectures were proven in [Jonsson, Electronic J. Combin., 13(1) (2006), R67]. There, it was also noted that the cylindrical case seemed to have interesting properties when the circumference of the cylinder is odd. In particular, when 3 is a divisor of both the circumference and the width of the cylinder minus 1, the partition function is -2. Otherwise, it is equal to 1. In this paper, we investigate the hard square and hard hexagon models at activity -1, with single periodic boundary, i.e, cylindrical identifications, using both topological and combinatorial techniques. We compute the homology groups of the associated independence complex for small sizes and suggest a matching which, we believe, with further analysis could help solve the conjecture. We also briefly review a technique recently described by Bousquet-M´elou, Linusson and Nevo, for determining some of the eigenvalues of the transfer matrix of the hard square model with cylindrical identification using a related, but more easily analysed model.

    National Category
    Mathematics
    Identifiers
    urn:nbn:se:liu:diva-12704 (URN)
    Available from: 2007-10-29 Created: 2007-10-29Bibliographically approved
  • 14.
    Thapper, Johan
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Applied Mathematics.
    Ett kombinatoriskt problem vid avrandomisering av algoritmer för stora CSP-problem2004In: Workshop i tillämpad matematik,2004, 2004Conference paper (Other academic)
  • 15.
    Thapper, Johan
    Linköping University, Department of Mathematics. Linköping University, Faculty of Arts and Sciences.
    Independence Complexes of Cylinders Constructed from Square and Hexagonal Grid GraphsManuscript (Other academic)
    Abstract [en]

    In the paper [Fendley et al., J. Phys. A: Math. Gen., 38 (2005), pp. 315-322], Fendley, Schoutens and van Eerten studied the hard square model at negative activity. They found analytical and numerical evidence that the eigenvalues of the transfer matrix with periodic boundary were all roots of unity. They also conjectured that for an m × n square grid, with doubly periodic boundary, the partition function is equal to 1 when m and n are relatively prime. These conjectures were proven in [Jonsson, Electronic J. Combin., 13(1) (2006), R67]. There, it was also noted that the cylindrical case seemed to have interesting properties when the circumference of the cylinder is odd. In particular, when 3 is a divisor of both the circumference and the width of the cylinder minus 1, the partition function is -2. Otherwise, it is equal to 1. In this paper, we investigate the hard square and hard hexagon models at activity -1, with single periodic boundary, i.e, cylindrical identifications, using both topological and combinatorial techniques. We compute the homology groups of the associated independence complex for small sizes and suggest a matching which, we believe, with further analysis could help solve the conjecture. We also briefly review a technique recently described by Bousquet-M´elou, Linusson and Nevo, for determining some of the eigenvalues of the transfer matrix of the hard square model with cylindrical identification using a related, but more easily analysed model.

  • 16.
    Thapper, Johan
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Refined Counting of Fully Packed Loop Configurations2007In: Séminaire Lotharingien de Combinatoire, ISSN 1286-4889, Vol. 56, p. 1-27Article in journal (Refereed)
    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.

1 - 16 of 16
CiteExportLink to result list
Permanent 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