Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 584 for “"approximation algorithms"”.
-
Consensus-type stochastic approximation algorithms
… with asymptotic properties of consensus-type algorithms for networked systems whose topologies switch randomly. The regime-switching process is modeled as a discrete-time Markov chain with a nite state space. The consensus control is achieved by designing stochastic approximation algorithms. …
-
Approximation Algorithms for Geometric Networks
The main contribution of this thesis is approximation algorithms for several computational geometry problems. The underlying structure for most of the problems studied is a geometric network. A geometric network is, in its abstract form, a set of vertices, pairwise connected with an edge, such that …
-
Approximation Algorithms for Resource Allocation
… is devoted to designing new techniques and algorithms for combinatorial optimization problems arising in various applications of resource allocation. Resource allocation refers to a class of problems where scarce resources must be distributed among competing agents maintaining certain …
-
Online Problems and Approximation Algorithms
… of classical techniques in developing algorithms for NP-hard problems, while also acknowledging the recent advancements in machine learning algorithms that provide new tools to these classic problems. This thesis focuses on online optimization problems, a type of discrete optimization …
-
Approximation algorithms for resource allocation optimization.
… the thesis focuses on the design and analysis of approximation algorithms. The main techniques we adopt are linear programming based, such as primal-dual schema, linear program rounding, and reductions via linear programs. Our developed solutions have great potential for optimizing the …
-
Approximation Algorithms for Graph Protection Problems
… scenarios. Our focus is on the design of approximation algorithms for Graph Protection when an ignition scenario can contain an arbitrary number of nodes, a setting mostly left open in the literature. Our main positive result is the design of constant-factor approximation algorithms for …
-
Approximation Algorithms for Rectangle Piercing Problems
… problem is NP-hard. Therefore we concentrate on approximation algorithms for the problem. As the known approximation ratio for arbitrarily sized rectangles is poor, we restrict our effort to designing approximation algorithms for unit-height rectangles. Our e-approximation scheme requires …
-
Approximation Algorithms for Illuminating 1.5D Terrain
… terrain is known to be NP-hard. We propose two approximation algorithms for covering 1.5D terrain by a fewer number of point guards. The first algorithm (Greedy Ranking Algorithm) is based on ranking vertices in term of number of visible edges from them. The second algorithm (Greedy Forward …
-
Approximation algorithms for multi-facility location
… the development and implementation of efficient algorithms to obtain acceptable solutions for the location of several facilities to serve customer sites. The general version of facility location problem is known to be NP-hard; For locating multiple facilities we use Voronoi diagram of initial …
-
Distributed approximation algorithms for graph problems
… two classical optimization problems in graph algorithms, namely the Minimum Weight Vertex Cover (MWVC) problem and the Maximum Weight Independent Set (MWIS) problem.<br>In the centralized setting, both problems are NP-hard on general graphs, and remain NP-hard even on restricted graph families …
-
Approximation Algorithms for Effective Team Formation
… cohesion and team size — and propose efficient algorithms for optimizing each in various settings. We show that under standard assumptions the problems we explore are not optimally solvable in polynomial time, and thus we focus on developing efficient algorithms with guaranteed worst case …
-
Certified Approximation Algorithms of Algebraic Curves
… it is important to know when the computed approximation is indeed a correct solution, which leads to the idea of a certified algorithm. An algorithm is said to be certified if it outputs both the solution to the problem and a certificate (a proof) that the solution is correct. In this …
-
Approximation Algorithms for Network Connectivity Problems
… connectivity problems, and achieve improved approximation algorithm and integrality gap results for them. We introduce an important new, highly useful and applicable, network connectivity problem - the Vital Core Connectivity Problem (VCC). Despite its many practical uses, this problem has …
-
Approximation Algorithms using Allegories and Coq
In this thesis, we implement several approximation algorithms for solving optimization problems on graphs. The result computed by the algorithm may or may not be optimal. The approximation factor of an algorithm indicates how close the computed result is to an optimal solution. We are going to …
-
Approximation algorithms for 2d packing problems
… problem we proposed a number of efficient algorithms which are able to find solutions within a factor of (1-\epsilon) of the optimum in polynomial time.
-
Approximation Algorithms for Geometric Packing Problems
In this thesis we present approximation algorithms for two-dimensional, geometric packing problems. We have given a set of rectangles that have to be placed in one or several predetermined target regions. Such packing problems can be found in several branches of industry, for example when placing …
-
Approximation algorithms for multidimensional bin packing
… bin packing problem has been the corner stone of approximation algorithms and has been extensively studied starting from the early seventies. In the classical bin packing problem, we are given a list of real numbers in the range (0, 1], the goal is to place them in a minimum number of bins so that …
-
Approximation algorithms on network resource allocation
Τα προβλήματα Ανάθεσης Πόρων (Resource Allocation Problems) θεωρούνται ιδιαίτερης σημασίας όχι μόνο από τη θεωρητική σκοπιά, αλλά επίσης λόγω των εφαρμογών τους στο σχεδιασμό δικτύων. Κεντρική θέση σε αυτήν την περιοχή κατέχουν τα επονομαζόμενα προβλήματα Τοποθέτησης Εργοστασίων (Facility Location …
Page 1 of 30