Search

Inspired by the seminal works of Khuller et al. (SIAM J. Comput. 25(2), 355–368 (1996)) and Chan (Discrete Comput. Geom. 32(2), 177–194 (2004)) we study the bottleneck version of the Euclidean bounded-degree spanning tree problem. A bottleneck spanning tree is a spanning tree whose largest edge-length is minimum, and a bottleneck degree-K spanning tree is a degree-K spanning tree whose largest edge-length is minimum. Let β K be the supremum ratio of the largest edge-length of the bottleneck degree-K spanning tree to the largest edge-length of the bottleneck spanning tree, over all finite point sets in the Euclidean plane. It is known that β 5 = 1 , and it is easy to verify that β 2 ⩾ 2 , β 3 ⩾ 2 , and β 4 > 1.175 . It is implied by the Hamiltonicity of the cube of the bottleneck spanning tree that β 2 ⩽ 3 . The degree-3 spanning tree algorithm of Ravi et al. (25th Annual ACM Symposium on Theory of Computing, pp. 438–447. ACM, New York (1993)) implies that β 3 ⩽ 2 . Andersen and Ras (Networks 68(4), 302–314 (2016)) showed that β 4 ⩽ 3 . We present the following improved bounds: β 2 ⩾ 7 , β 3 ⩽ 3 , and β 4 ⩽ 2 . As a result, we obtain better approximation algorithms for Euclidean bottleneck degree-3 and degree-4 spanning trees. As parts of our proofs of these bounds we present some structural properties of the Euclidean minimum spanning tree which are of independent interest. [ABSTRACT FROM AUTHOR]

Applications designed for data-parallel computation frameworks such as MapReduce usually alternate between computation and communication stages. Coflow scheduling is a recent popular networking abstraction introduced to capture such application-level communication patterns in datacenters. In this framework, a datacenter is modeled as a single non-blocking switch with m input ports and m output ports. A coflow j is a collection of flow demands { d io j } i ∈ { 1 , ... , m } , o ∈ { 1 , ... , m } that is said to be complete once all of its requisite flows have been scheduled. We consider the offline coflow scheduling problem with and without release times to minimize the total weighted completion time. Coflow scheduling generalizes the well studied concurrent open shop scheduling problem and is thus NP-hard. Qiu et al. (in: ACM Symposium on parallelism in algorithms and architectures. ACM, New York, pp 294–303, 2015) obtain the first constant approximation algorithms for this problem via LP rounding and give a deterministic 67 3 -approximation and a randomized (9 + 16 2 3) ≈ 16.54 -approximation algorithm. In this paper, we give a combinatorial algorithm that yields a deterministic 5-approximation algorithm for coflow scheduling with release times, and a deterministic 4-approximation for the case without release times. As for concurrent open shop problem with release times, we give a combinatorial 3-approximation algorithm. [ABSTRACT FROM AUTHOR]