Complexity of constraint satisfaction problems (Record no. 358240)
[ view plain ]
| 000 -LEADER | |
|---|---|
| fixed length control field | 02156ntm a22002417a 4500 |
| 003 - CONTROL NUMBER IDENTIFIER | |
| control field | AT-ISTA |
| 005 - DATE AND TIME OF LATEST TRANSACTION | |
| control field | 20190813102206.0 |
| 008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION | |
| fixed length control field | 170609s2017 au ||||| m||| 00| 0 eng d |
| 040 ## - CATALOGING SOURCE | |
| Transcribing agency | IST |
| 100 ## - MAIN ENTRY--PERSONAL NAME | |
| Personal name | Rolinek, Michal |
| 9 (RLIN) | 3357 |
| 245 ## - TITLE STATEMENT | |
| Title | Complexity of constraint satisfaction problems |
| 260 ## - PUBLICATION, DISTRIBUTION, ETC. (IMPRINT) | |
| Name of publisher, distributor, etc. | IST Austria |
| Date of publication, distribution, etc. | 2017 |
| 500 ## - GENERAL NOTE | |
| General note | Thesis |
| 505 ## - FORMATTED CONTENTS NOTE | |
| Formatted contents note | Acknowledgments |
| 505 ## - FORMATTED CONTENTS NOTE | |
| Formatted contents note | Abstract |
| 505 ## - FORMATTED CONTENTS NOTE | |
| Formatted contents note | 1 Introduction |
| 505 ## - FORMATTED CONTENTS NOTE | |
| Formatted contents note | 2 Complexity of valued CSP |
| 505 ## - FORMATTED CONTENTS NOTE | |
| Formatted contents note | 3 Generalizing Edmonds' algorithm |
| 505 ## - FORMATTED CONTENTS NOTE | |
| Formatted contents note | A Appendices |
| 520 ## - SUMMARY, ETC. | |
| Summary, etc. | An instance of the Constraint Satisfaction Problem (CSP) is given by a finite set of<br/>variables, a finite domain of labels, and a set of constraints, each constraint acting on<br/>a subset of the variables. The goal is to find an assignment of labels to its variables<br/>that satisfies all constraints (or decide whether one exists). If we allow more general<br/>“soft” constraints, which come with (possibly infinite) costs of particular assignments,<br/>we obtain instances from a richer class called Valued Constraint Satisfaction Problem<br/>(VCSP). There the goal is to find an assignment with minimum total cost.<br/>In this thesis, we focus (assuming that P<br/>6<br/>=<br/>NP) on classifying computational com-<br/>plexity of CSPs and VCSPs under certain restricting conditions. Two results are the core<br/>content of the work. In one of them, we consider VCSPs parametrized by a constraint<br/>language, that is the set of “soft” constraints allowed to form the instances, and finish<br/>the complexity classification modulo (missing pieces of) complexity classification for<br/>analogously parametrized CSP. The other result is a generalization of Edmonds’ perfect<br/>matching algorithm. This generalization contributes to complexity classfications in two<br/>ways. First, it gives a new (largest known) polynomial-time solvable class of Boolean<br/>CSPs in which every variable may appear in at most two constraints and second, it<br/>settles full classification of Boolean CSPs with planar drawing (again parametrized by a<br/>constraint language). |
| 856 ## - ELECTRONIC LOCATION AND ACCESS | |
| Uniform Resource Identifier | <a href="https://doi.org/10.15479/AT:ISTA:th_815">https://doi.org/10.15479/AT:ISTA:th_815</a> |
| 942 ## - ADDED ENTRY ELEMENTS (KOHA) | |
| Source of classification or shelving scheme | Dewey Decimal Classification |
| Withdrawn status | Lost status | Source of classification or shelving scheme | Damaged status | Not for loan | Home library | Current library | Date acquired | Total Checkouts | Full call number | Barcode | Date last seen | Price effective from | Koha item type |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Not Lost | Dewey Decimal Classification | Library | Library | 09/06/2017 | Quiet Room | AT-ISTA#001356 | 15/09/2025 | 09/06/2017 | Book |