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 17 of 17 for “"Competitive algorithms"”.
-
Competitive Algorithms and System for Multi-Robot Exploration of Unknown Environments
… ideas from information-theoretic exploration algorithms and computational geometry based exploration algorithms. The algorithm is based on a single-robot polygon exploration algorithm and a tree exploration algorithm. We show that the exploration time of our algorithm is competitive (as a …
-
On the practical viability of competitive algorithms for the homing online traveling salesperson problem: empirical evaluation and practical recommendations
… the metric space to serve requests. Although competitive algorithms such as Plan At Home (PAH) and Greedily Traveling between Requests (GTR) have been proposed under competitive analysis, their behavior under practical conditions remains largely untested. Competitive analysis reflects …
-
Trackless online two-server problems and red-black games
… a number of challenges in the search for simple competitive algorithms for solving it. Finding the optimal off-line solution involves costly dynamic programming. Looking for more efficient algorithms, researchers have studied how restriction on the input information given to the algorithm affects …
-
Online Network Design under Uncertainty
… k-server. We analyze their complexity and design competitive algorithms for them.
-
Polynomially searchable exponential neighbourhoods for sequencing problems in combinatorial optimisation
… Such neighbourhoods are used in local search algorithms for classes of combinatorial optimisation problems. We introduce a method, called dynasearch, of constructing new neighbourhoods, and of viewing some previously derived exponentially sized neighbourhoods which are searchable in polynomial …
-
Least square digital filter design in the frequency domain
… appears to converge more rapidly than other competitive algorithms. Unlike other frequency domain linearization methods, the new algorithm does not modify the error criterion. The fourth case includes an IIR filter design method with magnitude specification in the frequency domain. The …
-
Algorithms for Allocation Problems in Online Settings
… unrelated, and related—giving competitive algorithms for optimizing generic q-norms of the machines loads. In each setting we show these algorithm are optimal by giving asymptotically matching lower bounds. Also as a consequence of these results, we give the first constant …
-
Worst-case robot navigation in deterministic environments
We design and analyze algorithms for the following two robot navigation problems: 1. TARGET SEARCH. Given a robot located at a point s in the plane, how will a robot navigate to a goal t in the presence of unknown obstacles ? 2. LOCALIZATION. A robot is "lost" in an environment with a map of its …
-
Distributed redundant representations in man-made and biological sensing systems
… (e.g., video). We present a class of locally competitive algorithms (LCAs) that minimize a weighted combination of mean-squared error and a coefficient cost function. LCAs produce coefficients with sparsity levels comparable to centralized algorithms while being more realistic for physical …
-
Oblivious buy-at-bulk network design algorithms
… as how we can (obliviously) route flows and get competitive algorithms for this problem. We study the approximability of the resulting buy-at-bulk network design problem. Our aim is to _x000C_find minimum-cost paths for all the demands to the sink(s) under two assumptions: (1) The demand set is …
-
Vehicle Routing Problems
In this dissertation we consider variants of the vehicle routing problem applied to two problem areas. First, we consider the problem of scheduling deliveries from a central depot to clients in a metric space using a single delivery vehicle. Although this problem involves only a single vehicle …
-
Optimal Orchestration of a Cloud-Based Internet Cafe
… is presented for a cloud-based internet cafe and algorithms for maximising resource utilisation in cloud gaming. The cloud-based internet cafe model replaces the traditional desktop computers in an internet cafe with servers, thin clients, and virtual machines with specifications designed to meet …
-
Design of Scheduling Algorithms Using Game Theoretic Ideas
… theory and practice. In this thesis, we design algorithms that optimize {\em flow-time} (or delay) of jobs for scheduling problems that arise in a wide range of applications. We consider the classical model of unrelated machine scheduling and resolve several long standing open problems; we …
-
Domination : Offline, Online, Any Time
… of the graph connected at all times. We present algorithms that achieve 2-competitiveness on trees, 2.5-competitiveness on cactus graphs, (t-1) on K[subscript1],[subscript t]-free graphs, and [theta]([square root][delta]) for maximum degree [delta] graphs. Moreover, we show that all of those …
-
Generalized sequential assignment problem
… well-known Secretary Problem to derive constant-competitive algorithms for SSAP with tasks having a random arrival order. Several deterministic and randomized algorithms are proposed and their performance are compared with the maximum offline reward. These algorithms use the first stages of the …
-
NON-LINEAR AND SPARSE REPRESENTATIONS FOR MULTI-MODAL RECOGNITION
… computational complexity for sparse learning algorithms. Motivated by this observation, we introduce a novel framework, called <italic>sparse embedding<italic> (SE), for simultaneous dimensionality reduction and dictionary learning. We formulate an optimization problem for learning a …
-
Online scheduling algorithms for broadcasting and general cost functions
… concentrates on designing online scheduling algorithms and focuses mostly on broadcast scheduling, but also considers traditional scheduling on single and multiple machines. In the broadcast setting, clients send requests for pages of information. When the sever broadcast a page, all clients …