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

Direct link
BETA
Angelsmark, Ola
Publications (10 of 12) Show all publications
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
Angelsmark, O. & Thapper, J. (2006). Partitioning based algorithms for some colouring problems. In: Brahim Hnich, Mats Carlsson, François Fages and Francesca Rossi (Ed.), Recent Advances in Constraints: (pp. 44-58). Springer Berlin/Heidelberg, 3978
Open this publication in new window or tab >>Partitioning based algorithms for some colouring problems
2006 (English)In: 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.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2006
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 3978
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-48081 (URN)10.1007/11754602_4 (DOI)978-3-540-34215-1 (ISBN)3-540-34215-X (ISBN)
Available from: 2009-10-11 Created: 2009-10-11 Last updated: 2018-01-31Bibliographically approved
Angelsmark, O. & Thapper, J. (2005). A Microstructure Based Approach to Constraint Satisfaction Optimisation Problems. In: The 18th International FLAIRS Conference,2005 (pp. 155). Menlo Park, CA, USA: AAAI Press
Open this publication in new window or tab >>A Microstructure Based Approach to Constraint Satisfaction Optimisation Problems
2005 (English)In: The 18th International FLAIRS Conference,2005, Menlo Park, CA, USA: AAAI Press , 2005, p. 155-Conference paper, Published 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. 

Place, publisher, year, edition, pages
Menlo Park, CA, USA: AAAI Press, 2005
Keywords
Tvärvetenskap, artificial intelligence, constraint satisfaction, microstructure
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-24610 (URN)6786 (Local ID)6786 (Archive number)6786 (OAI)
Available from: 2009-10-07 Created: 2009-10-07 Last updated: 2018-01-13
Angelsmark, O. (2005). Constructing Algorithms for Constraint Satisfaction and Related Problems: Methods and Applications. (Doctoral dissertation). : Institutionen för datavetenskap
Open this publication in new window or tab >>Constructing Algorithms for Constraint Satisfaction and Related Problems: Methods and Applications
2005 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

In this thesis, we will discuss the construction of algorithms for solving Constraint Satisfaction Problems (CSPs), and describe two new ways of approaching them. Both approaches are based on the idea that it is sometimes faster to solve a large number of restricted problems than a single, large, problem. One of the strong points of these methods is that the intuition behind them is fairly simple, which is a definite advantage over many techniques currently in use.

The first method, the covering method, can be described as follows: We want to solve a CSP with n variables, each having a domain with d elements. We have access to an algorithm which solves problems where the domain has size e < d, and we want to cover the original problem using a number of restricted instances, in such a way that the solution set is preserved. There are two ways of doing this, depending on the amount of work we are willing to invest; either we construct an explicit covering and end up with a deterministic algorithm for the problem, or we use a probabilistic reasoning and end up with a probabilistic algorithm.

The second method, called the partitioning method, relaxes the demand on the underlying algorithm. Instead of having a single algorithm for solving problems with domain less than d, we allow an arbitrary number of them, each solving the problem for a different domain size. Thus by splitting, or partitioning, the domain of the large problem, we again solve a large number of smaller problems before arriving at a solution.

Armed with these new techniques, we study a number of different problems; the decision problems (d, l)-CSP and k-Colourability, together with their counting counterparts, as well as the optimisation problems Max Ind CSP, Max Value CSP, Max CSP, and Max Hamming CSP. Among the results, we find a very fast, polynomial space algorithm for determining k-colourability of graphs.

Place, publisher, year, edition, pages
Institutionen för datavetenskap, 2005. p. 171
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 947
Keywords
constraint satisfaction, CSP, graph problems, algorithm construction, computational complexity, microstructures, graph colouring, decision problems, optimisation problems, quantum computing, molecular computing
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-3836 (URN)91-85297-99-2 (ISBN)
Public defence
2005-06-03, Visionen, Hus B, Campus Valla, Linköping, 13:15 (English)
Opponent
Supervisors
Available from: 2005-09-20 Created: 2005-09-20 Last updated: 2018-01-13
Angelsmark, O. (2005). Partitioning based algorithms for some colouring problems. In: Proceedings of the Joint Annual Workshop of {ERCIM/CoLogNet} on Constraint Solving and Constraint Logic Programming,2005 (pp. 28-42). ERCIM
Open this publication in new window or tab >>Partitioning based algorithms for some colouring problems
2005 (English)In: Proceedings of the Joint Annual Workshop of {ERCIM/CoLogNet} on Constraint Solving and Constraint Logic Programming,2005, ERCIM , 2005, p. 28-42Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
ERCIM, 2005
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-31033 (URN)16740 (Local ID)16740 (Archive number)16740 (OAI)
Available from: 2009-10-09 Created: 2009-10-09 Last updated: 2018-01-13
Angelsmark, O. & Thapper, J. (2004). New Algorithms for the Maximum Hamming Distance Problem. In: Joint Annual Workshop of ERCIMCoLogNet on Constraint Solving and Constraint Logic Programming,2004 (pp. 271-285).
Open this publication in new window or tab >>New Algorithms for the Maximum Hamming Distance Problem
2004 (English)In: Joint Annual Workshop of ERCIMCoLogNet on Constraint Solving and Constraint Logic Programming,2004, 2004, p. 271-285Conference paper, Published paper (Refereed)
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-22135 (URN)1241 (Local ID)1241 (Archive number)1241 (OAI)
Available from: 2009-10-07 Created: 2009-10-07 Last updated: 2018-01-13
Angelsmark, O. & Jonsson, P. (2003). Improved algorithms for counting solutions in constraint satisfaction problems. In: Principles and Practice of Constraint Programming, 9th International Conference CP 2003,2003: . Paper presented at Constraint Programming 2003 (CP-2003) (pp. 81-95). Springer, 2833
Open this publication in new window or tab >>Improved algorithms for counting solutions in constraint satisfaction problems
2003 (English)In: Principles and Practice of Constraint Programming, 9th International Conference CP 2003,2003, Springer, 2003, Vol. 2833, p. 81-95Conference paper, Published paper (Refereed)
Abstract [en]

Counting the number of solutions to CSP instances has vast applications in several areas ranging from statistical physics to artificial intelligence. We provide a new algorithm for counting the number of solutions to binary CSP s which has a time complexity ranging from O ((d/4 . alpha(4))(n)) to O((alpha + alpha(5) + [d/4 - 1] . alpha(4))(n)) (where alpha approximate to 1.2561) depending on the domain size d greater than or equal to 3. This is substantially faster than previous algorithms, especially for small d. We also provide an algorithm for counting k-colourings in graphs and its running time ranges from O ([log(2) k](n)) to O ([log(2) k + 1](n)) depending on k greater than or equal to 4. Previously, only an O(1.8171(n)) time algorithm for counting 3-colourings were known, and we improve this upper bound to O(1.7879(n)).

Place, publisher, year, edition, pages
Springer, 2003
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 2833
National Category
Engineering and Technology Computer Sciences
Identifiers
urn:nbn:se:liu:diva-48440 (URN)10.1007/978-3-540-45193-8_6 (DOI)
Conference
Constraint Programming 2003 (CP-2003)
Available from: 2009-10-11 Created: 2009-10-11 Last updated: 2018-01-12
Angelsmark, O., Jonsson, P., Linusson, S. & Thapper, J. (2002). Determining the Number of Solutions to Binary CSP Instances. In: Principles and Practice of Constraint Programming, 8th International Conference CP-2002,2002 (pp. 327). Heidelberg: Springer Verlag
Open this publication in new window or tab >>Determining the Number of Solutions to Binary CSP Instances
2002 (English)In: Principles and Practice of Constraint Programming, 8th International Conference CP-2002,2002, Heidelberg: Springer Verlag , 2002, p. 327-Conference paper, Published 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. 

Place, publisher, year, edition, pages
Heidelberg: Springer Verlag, 2002
Keywords
Tvärvetenskap, constraint satisfaction, counting problems, CSP
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-24612 (URN)6788 (Local ID)6788 (Archive number)6788 (OAI)
Available from: 2009-10-07 Created: 2009-10-07 Last updated: 2018-01-13
Angelsmark, O., Dahllöf, V. & Jonsson, P. (2002). Finite Domain Constraint Satisfaction Using Quantum Computation. In: Mathematical Foundations of Computer Science, 27th International Symposium MFCS-2002,2002. Paper presented at MFCS-2002 (pp. 93). Heidelberg: Springer Verlag
Open this publication in new window or tab >>Finite Domain Constraint Satisfaction Using Quantum Computation
2002 (English)In: Mathematical Foundations of Computer Science, 27th International Symposium MFCS-2002,2002, Heidelberg: Springer Verlag , 2002, p. 93-Conference paper, Published paper (Refereed)
Abstract [en]

We present a quantum algorithm for finite domain constraint solving, where the constraints have arity 2. It is complete and runs in time, where d is size of the domain of the variables and n the number of variables. For the case of d=3 we provide a method to obtain an upper time bound of . Also for d=5 the upper bound has been improved. Using this method in a slightly different way we can decide 3-colourability in O(1.2185^n) time.

Place, publisher, year, edition, pages
Heidelberg: Springer Verlag, 2002
Series
Lecture Notes in Computer Science ; 2420
Keywords
constraint satisfaction, CSP, quantum computing
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-24611 (URN)6787 (Local ID)6787 (Archive number)6787 (OAI)
Conference
MFCS-2002
Available from: 2009-10-07 Created: 2009-10-07 Last updated: 2018-01-13
Organisations

Search in DiVA

Show all publications