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 4 of 4 for “"Polynomial-Time Approximation Algorithm"”.
-
High Multiplicity Strip Packing
… rectangle sizes and present an OPT + K - 1 polynomial-time approximation algorithm for it. This beats a previous algorithm with a worst case bound of OPT + K; the time complexity of that algorithm was not known and here we show that it runs in polynomial time.
-
On approximating projection games
… great significance in the field of hardness of approximation since almost all NP-hardness of approximation results known today are derived from the NP-hardness of approximation of projection games. Hence, it is important to determine the exact approximation ratio at which projection games become …
-
On Reducing Delays in P2P Live Streaming Systems
… has greatly enhanced the scalability of multimedia streaming on the Internet by enabling efficient cooperation among end-users. However, existing streaming applications are plagued by the problems of long playback latency and long churn-induced delays. First of all, many streaming …
-
Delay-Aware Multi-Path Routing in a Multi-Hop Network: Algorithms and Applications
… real-world routing applications including multimedia communication and freight delivery. Provisioning delay-minimal (or at least delay-bounded) routing services for all traffic of an application is highly important. As a basic paradigm of networking, multi-path routing has been proven to be …