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 6 of 6 for “"randomized rounding"”.
-
Constructing approximation algorithms via linear programming relaxations : primal dual and randomized rounding techniques
Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, 1996.
-
Clustering via matrix exponentiation
… mixture model involving planting a partition via randomized rounding of tailored matrix entries, the algorithm can be proven effective for only a single squaring. It is shown that the clustering performance of the algorithm degrades with larger values of the exponent, thus revealing that a single …
-
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>
-
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 …
-
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 …
-
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 …