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"”.

  1. 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 …

    waterloo Repository record for A 2-Approximation for the Height of Maximal Outerplanar Graph Drawings (opens in a new tab)

  2. 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 …

    waterloo Repository record for Iterative Rounding Approximation Algorithms in Network Design (opens in a new tab)

  3. 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 …

    unf Repository record for Sorting by Block Moves (opens in a new tab) Download PDF for Sorting by Block Moves (opens in a new tab)

  4. 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 …

    calpoly Repository record for Empirical Comparsion of Traveling Salesperson Approximation Algorithms (opens in a new tab)

  5. 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 …

    mcmaster Repository record for Batch Scheduling in Supply Chains (opens in a new tab)

  6. 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 …

    waterloo Repository record for Approximation Algorithms for Relative Survivable Network Design Problems (opens in a new tab)

  7. 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 …

    nps Repository record for Constant and power-of-2 segmentation algorithms for a high speed numerical function generator (opens in a new tab)

  8. 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 …

    unsw Repository record for Energy efficient multiple base stations deployment in wireless sensor networks (opens in a new tab)

  9. 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 …

    clemson Repository record for Approximation Algorithms for Network Interdiction and Fortification Problems (opens in a new tab)

  10. 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 …

    adelaide Repository record for Parameterised complexity analysis of evolutionary algorithms for combinatorial optimization problems (opens in a new tab)

  11. 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 …

    texas Repository record for Distributed fault tolerant distance computation in graphs : algorithms and lower bounds (opens in a new tab)

  12. 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.

    cornell Repository record for ROBUST MULTI-PRODUCT NEWSVENDOR PROBLEM UNDER A GLOBAL BUDGET OF UNCERTAINTY (opens in a new tab)

  13. 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 …

    mcmaster Repository record for Scheduling in Green Vehicular Infrastructure with Multiple Roadside Units (opens in a new tab)

  14. 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.

    ubc Repository record for Approximation algorithms for guarding 1.5 dimensional terrains (opens in a new tab) Download PDF for Approximation algorithms for guarding 1.5 dimensional terrains (opens in a new tab)

  15. 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 …

    texas Repository record for Darwinian evolution: the mutation of a weakly relativistic lagrangian (opens in a new tab)

  16. 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 …

    uiuc Repository record for New results on some quadratic programming problems (opens in a new tab)

  17. 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 …

    maryland Repository record for Algorithmic Approaches to Reducing Resource Costs in Data Centers (opens in a new tab)

  18. 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 …

    concordia Download PDF for Separation and Cover Problems in Temporal Graph (opens in a new tab)

Page 1 of 4