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 14 of 14 for “"randomized rounding"”.

  1. Survey of Approximation Algorithms for Set Cover Problem

    … Levin's improvement to Dur and Furer; 7. Simple rounding; 8. Randomized rounding; 9. LP duality; 10. Primal-dual schema; and 11. Network flow technique. Most of the algorithms surveyed are refinements of standard greedy algorithm.

    unt Repository record for Survey of Approximation Algorithms for Set Cover Problem (opens in a new tab)

  2. Using linear programming to minimize interference in wireless sensor networks

    … with a different interference model. Using randomized rounding, this relaxation gives an O(OPT*log n) approximation to this new problem. We then show that this solution is an O(OPT^2*log n) approximation to minimize the maximum interference using the standard interference model. If OPT=O(log …

    umn Repository record for Using linear programming to minimize interference in wireless sensor networks (opens in a new tab)

  3. Efficient Auction Mechanisms in the NFV Market

    … resources among mobile operators lever- aging randomized rounding, in both offline and online scenarios. The auction mechanisms we design run efficiently in polynomial time, guarantee truthfulness, and achieve near-optimal social welfare. The C-RAN online algorithm achieves a competitive ratio …

    calgary Repository record for Efficient Auction Mechanisms in the NFV Market (opens in a new tab)

  4. Online and offline algorithms for circuit switch scheduling

    … that combines the combinatorial greedy with randomized rounding of a different suitable linear program. For the online version of the problem, we present a (bi-criteria) ((e-1)/(2e-1)-epsilon)-competitive ratio (for any constant epsilon >0 ) that exceeds time by an additive factor of …

    gatech Repository record for Online and offline algorithms for circuit switch scheduling (opens in a new tab)

  5. Toward efficient online scheduling for large-scale distributed machine learning system

    … design; iii) We propose a meticulously designed randomized rounding approximation algorithm and rigorously prove its performance.Collectively, our results contribute to a comprehensive and fundamental understanding of distributed ML system optimization and algorithm design.</p>

    iastate Repository record for Toward efficient online scheduling for large-scale distributed machine learning system (opens in a new tab)

  6. Robust maximum covering location problem (RMCLP)

    … by the other approximate algorithm based on randomized rounding are within only nine percent of the Mean-Scenrio algorithm results, which proves the value of this approach.

    lethbridge Repository record for Robust maximum covering location problem (RMCLP) (opens in a new tab)

  7. Randomness as a Resource for Electric Power Systems

    … range of tasks, culminating in a unification of randomized rounding and differentiable optimization for efficiently solving graph-structured combinatorial optimization problems. A collection of power network topology control problems is then made tractable in the chapters that follow.

    gatech Repository record for Randomness as a Resource for Electric Power Systems (opens in a new tab)

  8. Approximation algorithms for the minimum congestion routing problem via k-route flows

    … that share a single edge). Early applications of randomized rounding introduced by Raghavan and Tompson provided a simple approximation algorithm for the case where k=1, but attempts to achieve similar approximation bounds in the case where k>1 have up until this point required the use of more …

    uiuc Repository record for Approximation algorithms for the minimum congestion routing problem via k-route flows (opens in a new tab)

  9. Cuts in Optimization and Approximation: Generalized MIR Cutting Plane and Integrality Gap Bounds for the Planar Multicut Problem

    … we introduce a generalized mixed-integer rounding (MIR) procedure that begins with systems of two equations, rather than a single equation as in the classical setting. This leads to a new family of valid inequalities for mixed-integer sets, whose derivation relies on structural results for …

    waterloo Repository record for Cuts in Optimization and Approximation: Generalized MIR Cutting Plane and Integrality Gap Bounds for the Planar Multicut Problem (opens in a new tab)

  10. On the Study of Fitness Landscapes and the Max-Cut Problem

    … the existence of a performance guarantee, the rounding step from the SDP solution to a Max-Cut solution is simple and randomized. For the Max-k-Cut problem, there exist several approximation algorithms but many of them have been proved to be equivalent. Similarly as in Max-Cut, these …

    qucosa-diss

  11. Capacity Characterization of Multi-Hop Wireless Networks- A Cross Layer Approach

    … based on combining mathematical programming with randomized rounding to obtain polynomial time approximation algorithms with provable worst case performance ratios. For the problems considered in this work, our results provide the best analytical performance guarantees currently known in the …

    vt Repository record for Capacity Characterization of Multi-Hop Wireless Networks- A Cross Layer Approach (opens in a new tab)

  12. Deep Multi-agent Reinforcement Learning for Efficient and Scalable Networked System Control

    … and reduce bandwidth consumption by employing randomized rounding to quantize each transmitted data piece, while only sending the non-zero components after quantization. Through the validation of two distinct CACC scenarios, our method has proven to outperform SOTA models in both control …

    msu Repository record for Deep Multi-agent Reinforcement Learning for Efficient and Scalable Networked System Control (opens in a new tab)

  13. Binary Multi-User Computation Offloading via Time Division Multiple Access

    … These include incremental and independent roundings, alongside an extended search that utilizes randomization-based methods in both rounding schemes. The findings reveal that incremental randomized rounding, when applied to the normal approximation of the rate limits, enhances system …

    mcmaster Repository record for Binary Multi-User Computation Offloading via Time Division Multiple Access (opens in a new tab)

  14. Subset Selection via Spectral Objectives

    … the natural convex program, and randomly rounding the optimal solution, we are able to find (1-epsilon)-approximate solution in polynomial time, when the dimension of the vectors is constant. Finally, we turn to a practical problem in electrical network design called the network …

    gatech Repository record for Subset Selection via Spectral Objectives (opens in a new tab)