On Infinite-Domain CSPs Parameterized by Solution Cost

On Infinite-Domain CSPs Parameterized by Solution Cost
Author :
Publisher : Linköping University Electronic Press
Total Pages : 53
Release :
ISBN-10 : 9789180754972
ISBN-13 : 918075497X
Rating : 4/5 (72 Downloads)

Book Synopsis On Infinite-Domain CSPs Parameterized by Solution Cost by : George Osipov

Download or read book On Infinite-Domain CSPs Parameterized by Solution Cost written by George Osipov and published by Linköping University Electronic Press. This book was released on 2024-04-24 with total page 53 pages. Available in PDF, EPUB and Kindle. Book excerpt: In this thesis we study the computational complexity of MinCSP - an optimization version of the Constraint Satisfaction Problem (CSP). The input to a MinCSP is a set of variables and constraints applied to these variables, and the goal is to assign values (from a fixed domain) to the variables while minimizing the solution cost, i.e. the number of unsatisfied constraints. We are specifically interested in MinCSP with infinite domains of values. Infinite-domain MinCSPs model fundamental optimization problems in computer science and are of particular relevance to artificial intelligence, especially temporal and spatial reasoning. The usual way to study computational complexity of CSPs is to restrict the types of constraints that can be used in the inputs, and either construct fast algorithms or prove lower bounds on the complexity of the resulting problems. The vast majority of interesting MinCSPs are NP-hard, so standard complexity-theoretic assumptions imply that we cannot find exact solutions to all inputs of these problems in polynomial time with respect to the input size. Hence, we need to relax at least one of the three requirements above, opting for either approximate solutions, solving some inputs, or using super-polynomial time. Parameterized algorithms exploits the latter two relaxations by identifying some common structure of the interesting inputs described by some parameter, and then allowing super-polynomial running times with respect to that parameter. Such algorithms are feasible for inputs of any size whenever the parameter value is small. For MinCSP, a natural parameter is optimal solution cost. We also study parameterized approximation algorithms, where the requirement for exact solutions is also relaxed. We present complete complexity classifications for several important classes of infinite-domain constraints. These are simple temporal constraints and interval constraints, which have notable applications in temporal reasoning in AI, linear equations over finite and infinite fields as well as some commutative rings (e.g., the rationals and the integers), which are of fundamental theoretical importance, and equality constraints, which are closely related to connectivity problems in undirected graphs and form the basis of studying first-order definable constraints over infinite domains. In all cases, we prove results as follows: we fix a (possibly infinite) set of allowed constraint types C, and for every finite subset of C, determine whether MinCSP(), i.e., MinCSP restricted to the constraint types in , is fixed-parameter tractable, i.e. solvable in f(k) · poly(n) time, where k is the parameter, n is the input size, and f is any function that depends solely on k. To rule out such algorithms, we prove lower bounds under standard assumptions of parameterized complexity. In all cases except simple temporal constraints, we also provide complete classifications for fixed-parameter time constant-factor approximation.


On Infinite-Domain CSPs Parameterized by Solution Cost Related Books

On Infinite-Domain CSPs Parameterized by Solution Cost
Language: en
Pages: 53
Authors: George Osipov
Categories:
Type: BOOK - Published: 2024-04-24 - Publisher: Linköping University Electronic Press

DOWNLOAD EBOOK

In this thesis we study the computational complexity of MinCSP - an optimization version of the Constraint Satisfaction Problem (CSP). The input to a MinCSP is
Companion Robots for Older Adults
Language: en
Pages: 175
Authors: Sofia Thunberg
Categories:
Type: BOOK - Published: 2024-05-06 - Publisher: Linköping University Electronic Press

DOWNLOAD EBOOK

This thesis explores, through a mixed-methods approach, what happens when companion robots are deployed in care homes for older adults by looking at different p
Empirical Studies in Machine Psychology
Language: en
Pages: 201
Authors: Robert Johansson
Categories:
Type: BOOK - Published: 2024-10-09 - Publisher: Linköping University Electronic Press

DOWNLOAD EBOOK

This thesis presents Machine Psychology as an interdisciplinary paradigm that integrates learning psychology principles with an adaptive computer system for the
Emergency Vehicle Approaching
Language: en
Pages: 115
Authors: Kajsa Weibull
Categories:
Type: BOOK - Published: 2024-10-17 - Publisher: Linköping University Electronic Press

DOWNLOAD EBOOK

Driving an emergency vehicle can be difficult. The driver of the emergency vehicle must navigate, communicate with emergency services, often drive at high speed
Orchestrating a Resource-aware Edge
Language: en
Pages: 122
Authors: Klervie Toczé
Categories:
Type: BOOK - Published: 2024-09-02 - Publisher: Linköping University Electronic Press

DOWNLOAD EBOOK

More and more services are moving to the cloud, attracted by the promise of unlimited resources that are accessible anytime, and are managed by someone else. Ho