Sökning: "randomized algorithms"

Visar resultat 1 - 5 av 24 avhandlingar innehållade orden randomized algorithms.

1. 1. Studies in Efficient Discrete Algorithms

   Författare :DZMITRY SLEDNEU; Matematik (naturvetenskapliga fakulteten); []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; NATURVETENSKAP; NATURAL SCIENCES; Algorithms; Approximation algorithms; Graphs;

   Sammanfattning : This thesis consists of five papers within the design and analysis of efficient algorithms.In the first paper, we consider the problem of computing all-pairs shortest paths in a directed graph with real weights assigned to vertices. We develop a combinatorial randomized algorithm that runs in subcubic time for a special class of graphs. LÄS MER

3. 2. Some new randomized approximation algorithms

   Författare :Gunnar Andersson; KTH; []
   Nyckelord :;

   Sammanfattning : .... LÄS MER

4. 3. First-Order Algorithms for Communication Efficient Distributed Learning

   Författare :Sarit Khirirat; Mikael Johansson; Martin Jaggi; KTH; []
   Nyckelord :TEKNIK OCH TEKNOLOGIER; ENGINEERING AND TECHNOLOGY; Communication efficient learning; Optimization algorithms; Quantization; Error compensation; First-order algorithms; Stochastic gradient descent; Tillämpad matematik och beräkningsmatematik; Applied and Computational Mathematics; Optimeringslära och systemteori; Optimization and Systems Theory; Electrical Engineering; Elektro- och systemteknik;

   Sammanfattning : Technological developments in devices and storages have made large volumes of data collections more accessible than ever. This transformation leads to optimization problems with massive data in both volume and dimension. LÄS MER

5. 4. Combinatorial Optimization for Infinite Games on Graphs

   Författare :Henrik Björklund; Sergei Vorobyov; Erich Grädel; Uppsala universitet; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; infinite games; combinatorial optimization; randomized algorithms; model checking; strategy evaluation functions; linear programming; iterative improvement; local search; Computer science; Datavetenskap;

   Sammanfattning : Games on graphs have become an indispensable tool in modern computer science. They provide powerful and expressive models for numerous phenomena and are extensively used in computer- aided verification, automata theory, logic, complexity theory, computational biology, etc. LÄS MER

7. 5. Algorithmic Bounds for Presumably Hard Combinatorial Problems

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

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