In the Constraint Satisfaction Problem (CSP) one is supposed to find an assignment to a set of variables so that a set of given constraints are satisfied. Many problems, both practical and theoretical, can be modelled as CSPs. As these problems are computationally hard it is interesting to investigate what kind of restrictions of the problems implies computational tractability. In this thesis the computational complexity of restrictions of two optimisation problems which are related to the CSP is studied. In optimisation problems one can also relax the requirements and ask for an approximatively good solution, instead of requiring the optimal one. The first problem we investigate is Maximum Solution (Max Sol) where one is looking for a solution which satisfies all constraints and also maximises a linear bjective function. The Maximum Solution problem is a generalisation of the well-known integer linear programming problem. In the case when the constraints are equations over an abelian group we obtain tight inapproximability results. We also study Max Sol for so-called maximal constraint languages and a partial classification theorem is obtained in this case. Finally, Max Sol over the boolean domain is studied in a setting where each variable only occurs a bounded number of times. The second problem is the Maximum Constraint Satisfaction Problem (Max CSP). In this problem one is looking for an assignment which maximises the number of satisfied constraints. We first show that if the constraints are known to give rise to an NP-hard CSP, then one cannot get arbitrarily good approximate solutions in polynomial time, unless P = NP. We use this result to show a similar hardness result for the case when only one constraint relation is used. We also study the submodular function minimisation problem (SFM) on certain finite lattices. There is a strong link between Max CSP and SFM; new tractability results for SFM implies new tractability results for Max CSP. It is conjectured that SFM is the only reason for Max CSP to be tractable, but no one has yet managed to prove this. We obtain new tractability results for SFM on diamonds and evidence which supports the hypothesis that all modular lattices are tractable. / I ett villkorsprogrammeringsproblem är uppgiften att tilldela värden till variabler så att en given mängd villkor blir uppfyllda. Många praktiska problem, så som schemaläggning och planering, kan formuleras som villkorsprogrammeringsproblem och det är därför önskvärt att ha effektiva algoritmer för att hitta lösningar till denna typ av problem. De generella varianterna av dessa problem är NP-svåra att lösa. Detta innebär att det antagligen inte finns effektiva algoritmer för problemen (om inte P = NP vilket anses vara mycket osannolikt). Av denna anledning förenklar vi problemet genom att studera restriktioner av det och ibland nöjer vi oss med approximativa lösningar. I den här avhandlingen studeras två varianter av villkorsprogrammeringsproblemet där man inte bara ska hitta en lösning utan hitta en så bra lösning som möjligt. I den första varianten är målet att hitta en tilldelning där samtliga villkor uppfylls och att en viktad summa av variablerna maximeras. Detta problem kan ses som en generalisering av det välkända linjära heltalsprogrammeringsproblemet. I den andra varianten är målet att hitta en tilldelning som uppfyller så många villkor som möjligt. Då det gäller den första varianten, då man ska hitta en lösning som uppfyller samtliga villkor som också maximerar summan av variablerna, presenteras nya resultat för ett antal specialfall. De så kallade maximala villkorsmängderna studeras och komplexiteten för ett antal av dessa bestäms. Vi studerar också en variant av problemet över den Boolska domänen då antal variabelförekomster är begränsat. I detta fall ger vi en partiell klassifikation över vilka villkorsmängder som är hanterbara och vilka som inte kan lösas effektivt. För den andra varianten, då man ska uppfylla så många villkor som möjligt, presenteras några nya effektiva algoritmer för vissa restriktioner. I dessa algoritmer löses det mer generella problemet av minimering av submodulära funktioner över vissa ändliga latticar. Vi bevisar också ett resultat som beskriver exakt när det finns effektiva algoritmer då man endast har tillgång till en typ av villkor.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:liu-51687 |
| Date | January 2009 |
| Creators | Kuivinen, Fredrik |
| Publisher | Linköpings universitet, TCSLAB - Laboratoriet för teoretisk datalogi, Linköpings universitet, Tekniska högskolan, Linköping : Linköping University Electronic Press |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Doctoral thesis, monograph, info:eu-repo/semantics/doctoralThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | Linköping Studies in Science and Technology. Dissertations, 0345-7524 ; 1274 |
Page generated in 0.002 seconds