Sökning: "Computational Hardness"

Visar resultat 1 - 5 av 39 avhandlingar innehållade orden Computational Hardness.

  1. 1. On Cooperative Surveillance, Online Trajectory Planning and Observer Based Control

    Författare :David A. Anisi; Xiaoming Hu; Randal Beard; KTH; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Surveillance Missions; Minimum-Time Surveillance; Unmanned Ground Vehicles; Connectivity Constraints; Combinatorial Optimization; Computational Optimal Control; Receding Horizon Control; Mission Uncertainty; Safety; Task Completion; Adaptive Grid Methods; Missile Guidance; Nonlinear Observer Design; Active Observers; Non--uniformly Observable Systems; Mobile Robotic Systems; Intrinsic Observers; Differential Geometric Methods; Euler-Lagrange Systems; Contraction Analysis.; Optimization; systems theory; Optimeringslära; systemteori; Applied mathematics; Tillämpad matematik;

    Sammanfattning : The main body of this thesis consists of six appended papers. In the  first two, different  cooperative surveillance problems are considered. The second two consider different aspects of the trajectory planning problem, while the last two deal with observer design for mobile robotic and Euler-Lagrange systems respectively. LÄS MER

  3. 2. Hardness of Constraint Satisfaction and Hypergraph Coloring : Constructions of Probabilistically Checkable Proofs with Perfect Completeness

    Författare :Sangxia Huang; Johan Håstad; Rishi Saket; KTH; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Combinatorial optimization; approximation; inapproximability; hardness; probabilistically checkable proofs; pcp; perfect completeness; boolean constraint satisfaction problem; csp; graph coloring; hypergraph coloring; direct sum; superposition; label cover; Computer Science; Datalogi;

    Sammanfattning : A Probabilistically Checkable Proof (PCP) of a mathematical statement is a proof written in a special manner that allows for efficient probabilistic verification. The celebrated PCP Theorem states that for every family of statements in NP, there is a probabilistic verification procedure that checks the validity of a PCP proof by reading only 3 bits from it. LÄS MER

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

    Författare :Cenny Wenner; Johan Håstad; Viggo Kann; Irit Dinur; Stockholms universitet; []
    Nyckelord :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;

    Sammanfattning : 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). LÄS MER

  5. 4. Computational problems in evolution : Multiple alignment, genome rearrangements, and tree reconstruction

    Författare :Isaac Elias; Jens Lagergren; Lior Pachter; KTH; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Distance Methods; Tree reconstruction; Sorting by Transpositions; multiple alignment; ancestral sequences; Computer science; Datavetenskap;

    Sammanfattning : Reconstructing the evolutionary history of a set of species is a fundamental problem in biology. This thesis concerns computational problems that arise in different settings and stages of phylogenetic tree reconstruction, but also in other contexts. LÄS MER

  7. 5. ICME guided development of cemented carbides with alternative binder systems

    Författare :Martin Walbrühl; John Ågren; Annika Borgenstam; Henrik Larsson; Claudio Miguel Lousada Patricio; Jan Qvick; KTH; []
    Nyckelord :TEKNIK OCH TEKNOLOGIER; ENGINEERING AND TECHNOLOGY; Cemented carbide; ICME; Materials Design; alternative binder; hardness; AIMD; liquid diffusion; frozen-in solubilities; DICTRA; surface gradients; labyrinth factor; Materials Science and Engineering; Teknisk materialvetenskap;

    Sammanfattning : The development of alternative binder systems for tungsten carbide (WC) based cemented carbides has again become of relevance due to possible changes in EU regulations regarding the use of Cobalt (Co). A framework for the ICME (Integrated Computational Materials Engineering) based Materials Design is presented to accelerate the development of alternative binder systems. LÄS MER