Search for dissertations about: "NP-hard"

Showing result 1 - 5 of 51 swedish dissertations containing the word NP-hard.

  2. 1. 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

  4. 2. 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

  5. 3. 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

  6. 4. On the optimization of opportunistic maintenance activities

    Author : Adam Wojciechowski; Göteborgs universitet; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; mixed integer linear programming; stochastic programming; complexity theory; mixed integer linear programming; complexity theory; stochastic programming;

    Abstract : Maintenance is a source of large costs; in the EU the maintenance costs amountto between 4% and 8% of the total sales turnover. Opportunistic maintenance is anattempt to lower the maintenance cost by considering the failure of onecomponent as an opportunity to replace yet non-failed components in order toprevent future failures. READ MORE

  7. 5. Crowdsensing-driven Route Optimisation Algorithms for Smart Urban Mobility

    Author : Petar Mrazovic; Mihhail Matskin; Anne Håkansson; Josep Luis Larriba-Pey; Roman Dumitru; KTH; []
    Keywords : TEKNIK OCH TEKNOLOGIER; ENGINEERING AND TECHNOLOGY; smart cities; smart mobility; urban mobility; mobile crowdsensing; route journey planning; route optimisation; heuristic algorithms; smarta städer; smart rörlighet; rörlighetsavkänning; mobil publikmätning; ruttplanering; ruttoptimering; heuristiska algoritmer; Ciudades inteligentes; movilidad inteligente; mobile crowdsensing; planificación de viajes rutas; optimización de rutas; algoritmos heurísticos; Informations- och kommunikationsteknik; Information and Communication Technology;

    Abstract : Urban mobility is often considered as one of the main facilitators for greener and more sustainable urban development. However, nowadays it requires a significant shift towards cleaner and more efficient urban transport which would support for increased social and economic concentration of resources in cities. READ MORE