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 13 of 13 for “"Approximation Factor"”.
-
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 …
-
Facility location and the analysis of algorithms through factor-revealing programs
… much effort has been devoted to designing approximation algorithms for it. As our main result, we introduce a method called dual fitting and use it in conjunction with factor-revealing programs to obtain improved approximation algorithms for the UFLP. Our best algorithm achieves an …
-
Algorithmic embeddings
… and the distortion of the embedding is the factor by which the distances change. We have pioneered theoretical work on relative (or approximation) version of this problem. In this setting, the question is the following: for the class of metrics C, and a host metric M', what is the smallest …
-
Three essays on sequencing and routing problems
… of problems are sequencing problems. We study approximation algorithms and local search heuristics for these problems. First, we analyze the Vehicle Routing Problem (VRP) with and without split deliveries. In this problem, we have to route vehicles from the depot to deliver the demand to the …
-
New sublinear methods in the struggle against classical problems
We study the time and query complexity of approximation algorithms that access only a minuscule fraction of the input, focusing on two classical sources of problems: combinatorial graph optimization and manipulation of strings. The tools we develop find applications outside of the area of sublinear …
-
Fair allocation of operations and makespan minimization for multiple robotic agents
We study the problem of allocating a set of indivisible operations to a set of agents in a fair and efficient manner while also minimizing the makespan. We first present the Operation Trading Algorithm that generates allocations satisfying the DEQx (Duplicated Equitability up to any operation) …
-
Scalable and Efficient Graph Algorithms and Analysis Techniques for Modern Machines
… and show improvements in number of rounds and approximation factor, compared to the previous state-of-the-art, in real-world graphs. We conclude this part with a near-linear time scheduling algorithm for scheduling on identical machines with communication delay where precedence constrained jobs …
-
Finding Patterns, Short Cycles and Long Shortest Paths in Graphs
… is known to be hard. There is a folklore 2- approximation algorithm for the diameter that works in linear time, and we show that this algorithm is optimal conditioned on the Strong Exponential Time Hypothesis (SETH). Our result shows that any better than 2-approximation algorithm for the …
-
Fault tolerant Euclidean K-Centers
… an O(nk/ℓ)-time algorithm that computes a 2-approximation, offering an efficient and practical solution with provable guarantees.
-
Approximation algorithms for spectrum allocation and power control in wireless networks
… of capacity maximization, we present constant-factor approximations. In the case of latency-minimization, they directly yield centralized O(log n)-approximation algorithms. We also analyze a distributed algorithm for latency minimization with fixed transmit powers and show it to be an O(log² …
-
New Models And Algorithms For Distribution Testing: Beyond Standard Sampling
… if the predictor is correct up to a constant approximation factor, then the sample complexity can be reduced significantly, to log(1/𝜀)· 𝑁¹⁻ᶿ⁽¹⸍ ˡᵒᵍ⁽¹⸍𝜀⁾⁾ . In addition, we evaluate the proposed algorithms on a collection of data sets, using the neural-network based estimators from Hsu et al. …
-
On Reducing Delays in P2P Live Streaming Systems
… We then present a polynomial-time approximation algorithm, called Fastream-I, for this problem, and show that the performance of Fastream-I is bounded by a ratio of O(SQRT(log n)), where n is the number of peers in the system. We also develop a distributed version of Fastream-I that …
-
The complexity of Nash Equilibria, Local Optima, and Pareto-Optimal solutions
… instances both with respect to running time and approximation ratio. We present, for every p, a family of two-dimensional Lp instances on which 2-Opt can take an exponential number of steps. In order to explain the discrepancy between this worst-case result and the observations in practice, we …