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 79 for “"2-approximation"”.
-
A 2-Approximation for the Height of Maximal Outerplanar Graph Drawings
… at least ud(G) + 1, which makes our result a 2-approximation for the optimal height. The best previously known approximation algorithm gave a 4-approximation. In addition, we provide an algorithm for finding the umbrella depth of G in linear time. Lastly, we compare the umbrella depth to other …
-
Iterative Rounding Approximation Algorithms in Network Design
… introduced the concept in his revolutionary 2-approximation for the Survivable Network Design Problem (SNDP). This paper looks at several important iterative rounding approximation algorithms and makes improvements to some of their proofs. We generalize a matrix restatement of Nagarajan et …
-
Sorting by Block Moves
… extensively and now there are several 2-approximation algorithms for its solution. This work introduces new structures on a permutation, which are called runs and ordered pairs, and are used to develop two new approximation algorithms. Both the new algorithms are 2-approximation …
-
Empirical Comparsion of Traveling Salesperson Approximation Algorithms
… in general, but special cases have many approximation algorithms, which come with tradeoffs. In this thesis we compare the runtime, approximation ratio, and overall implementation complexity of two approximation algorithms for the Euclidean version of the problem, a classical …
-
Batch Scheduling in Supply Chains
… weights are intractable. We provide a 2-approximation algorithm for this problem. The performance of this 2-approximation algorithm shows that it provides close to optimal solutions for practical situations. Batch scheduling problems at the manufacturer of multi-product case is …
-
Approximation Algorithms for Relative Survivable Network Design Problems
… if some edges ”fail”. It is well known that a 2-approximation algorithm for SND exists, using the method of iterative rounding. In 2022, Dinitz et al. introduced a problem that we refer to as Path-Relative Survivable Network Design (PRSND), a natural extension of SND that addresses cases where …
-
Constant and power-of-2 segmentation algorithms for a high speed numerical function generator
… [Ref.1]. The first algorithm is the Constant Approximation. This algorithm uses lines of slope zero to approximate a curve. The second algorithm is the power-of-2-approximation. This method uses 2i x to approximate a curve. The constant approximation eliminates the need for a multiplier and …
-
Energy efficient multiple base stations deployment in wireless sensor networks
… the clusters of a WSN. Secondly, we propose a 2-approximation algorithm for minimizing the shortest hop distance from all the sensor nodes to the designated base stations in order to deploy k base stations in a WSN. For a single base station, we present an optimal algorithm for finding the …
-
Approximation Algorithms for Network Interdiction and Fortification Problems
… disconnected from each other. We investigate an approximation algorithm for general r with a relatively simple analysis guaranteeing an approximation ratio ≤ 1.4647 − epsilonr, where epsilonr is a small constant related to the number of terminals r. This improves on the 1.5 − 1/r guarantee of …
-
Parameterised complexity analysis of evolutionary algorithms for combinatorial optimization problems
… with respect to their ability to maintain a 2-approximation. Inspired by the concept of duality, an edge-based evolutionary algorithm for solving the VCP has been introduced in the literature. Here we show that this edge-based EA is able to maintain a 2-approximation solution in the dynamic …
-
Distributed fault tolerant distance computation in graphs : algorithms and lower bounds
… round complexity, including a novel sublinear 2-approximation algorithm for directed MWC and an algorithm that closes a longstanding gap for 2-approximation of undirected unweighted MWC (girth). Together, our results display a rich landscape of distributed round complexity for exact and …
-
ROBUST MULTI-PRODUCT NEWSVENDOR PROBLEM UNDER A GLOBAL BUDGET OF UNCERTAINTY
… For the general n item problem, we present a 2-approximation algorithm and demonstrate its asymptotic optimality. The experimental results confirm the value of the approximation algorithm and indicate that the average performance is close to optimal.
-
Scheduling in Green Vehicular Infrastructure with Multiple Roadside Units
… the SRA case there is a polynomial complexity 2-approximation bound for the normalized min-max energy schedule. These bounds are used for comparisons with several proposed online scheduling algorithms. The first scheduler is a low complexity Greedy Online Algorithm (GOA) that makes greedy RSU …
-
Approximation algorithms for guarding 1.5 dimensional terrains
… though no attempt has been made to minimize the approximation factor. We give a 4-approximation algorithm for the general 1.5D terrain guarding problem, as well as a 2-approximation algorithm for the case with upwardlooking guards, i.e. when guards cannot see vertices that are below themselves.
-
Darwinian evolution: the mutation of a weakly relativistic lagrangian
The work studies Darwin’s order-(v/c)2 approximation to the relativistic interaction of classical charged particles. The first part presents an in- troduction to the methods of symplectic reduction in the Newtonian two- body problem and then applies these to a two-body Darwin interaction. The …
-
New results on some quadratic programming problems
… the explored relation to develop effective approximation algorithms. For example, the first problem we consider is a special class of binary quadratic problem where the number of nonzero elements is fixed. We use convex quadratic relaxation as a geometric embedding tool to reformulate the …
-
Algorithmic Approaches to Reducing Resource Costs in Data Centers
… budget, for which we give 1/2 - O(epsilon) approximation algorithms; 2) minimizing the maximum temperature when all jobs have to be scheduled, for which we give a 2-approximation algorithm and a 3-competitive online algorithm for a single rack of machines, where the factors approach 4/3 and …
-
Separation and Cover Problems in Temporal Graph
… Separator problem. We present a τ-approximation algorithm for (s,z)-Temporal Separator problem, and we convert it to a τ^2-approximation algorithm for (s,z,t)-Temporal Separator problem. We also present an inapproximability lower bound of Ω(ln(n) + ln(τ)) for (s,z,t)-Temporal …
Page 1 of 4