Search for dissertations about: "NP HARD"

Showing result 1 - 5 of 56 swedish dissertations containing the words NP HARD.

2. 1. Algorithmic Bounds for Presumably Hard Combinatorial Problems

   Author : Andreas Björklund; Institutionen för datavetenskap; []
   Keywords : NATURVETENSKAP; NATURAL SCIENCES; numerisk analys; system; control; Datalogi; numerical analysis; systems; Computer science; Approximation algorithms; Exact algorithms; NP-hard problems; Algorithm theory; kontroll;

   Abstract : In this thesis we present new worst case computational bounds on algorithms for some of the most well-known NP-complete and #P-complete problems and their optimization variants. We consider graph problems like Longest Path, Maximum Cut, Number of Perfect Matchings, Chromatic and Domatic Number, as well as Maximum k-Satisfiability and Set Cover. READ MORE

4. 2. Label Cover Reductions for Unconditional Approximation Hardness of Constraint Satisfaction

   Author : Cenny Wenner; Johan Håstad; Viggo Kann; Irit Dinur; Stockholms universitet; []
   Keywords : NATURVETENSKAP; NATURAL SCIENCES; Combinatorial Optimization; Complexity Theory; Approximation; Approximability; Inapproximability; Computational Hardness; NP; Optimization; Constraint Satisfaction; Kombinatorisk optimering; Komplexitetsteori; Beräkningsteori; Approximation; Approximerbarhet; Beräkningssvårighet; NP; Optimering; Vilkorssatisfiering; Vilkorsuppfyllning; Vilkorstillfredställand; datalogi; Computer Science;

   Abstract : Combinatorial optimization include such tasks as finding the quickest route to work, scheduling jobs to specialists, and placing bus stops so as to minimize commuter times. We consider problems where one is given a collection of constraints with the objective of finding an assignment satisfying as many constraints as possible, also known as Constraint Satisfaction Problems (CSPs). READ MORE

5. 3. Optimization of Joint Cell, Channel and Power Allocation in Wireless Communication Networks

   Author : Mikael Fallgren; Anders Forsgren; Zhi-Quan (Tom) Luo; KTH; []
   Keywords : NATURVETENSKAP; NATURAL SCIENCES; TEKNIK OCH TEKNOLOGIER; ENGINEERING AND TECHNOLOGY; TEKNIK OCH TEKNOLOGIER; ENGINEERING AND TECHNOLOGY; Wireless multicell networks; Optimization; OFDMA; Shannon capacity; Complexity; NP-hard; Relays; Allocation problems; Heuristic algorithms;

   Abstract : In this thesis we formulate joint cell, channel and power allocation problems within wireless communication networks. The objectives are to maximize the user with mini- mum data throughput (Shannon capacity) or to maximize the total system throughput, referred to as the max-min and max-sum problem respectively. READ MORE

6. 4. Label Cover Reductions for Unconditional Approximation Hardness of Constraint Satisfaction

   Author : Cenny Wenner; Johan Håstad; Irit Dinur; Numerical Analysis and Computer Science (NADA) Faculty of Science Stockholm University; []
   Keywords : NATURVETENSKAP; NATURAL SCIENCES; Optimization; NP; Approximation; Approximability; Inapproximability; Constraint Satisfaction; CSP; Boolean Analysis; Satisfiability; SAT; Acyclic Subgraph; Betweenness; Unique Games; Computer Science; Datalogi;

   Abstract : Problem solving is an integral aspect of modern society and includes such tasks as picking the fastest route to work, optimizing a production line, scheduling computer tasks, placing new bus stops, or picking a meal from available ingredients.We study the hardness of solving Constraint Satisfaction Problems (CSPs). READ MORE

7. 5. Exact Algorithms for Exact Satisfiability Problems

   Author : Vilhelm Dahllöf; Peter Jonsson; Fedor Fomin; Linköpings universitet; []
   Keywords : NATURVETENSKAP; NATURAL SCIENCES; NP-hardness; exact algorithms; satisfiability; exact satisfiability; Computer science; Datalogi;

   Abstract : This thesis presents exact means to solve a family of NP-hard problems. Starting with the well-studied Exact Satisfiability problem (XSAT) parents, siblings and daughters are derived and studied, each with interesting practical and theoretical properties. READ MORE