Search

Given a connected graph G = (V , E) , we seek to partition the vertex set V into k non-empty parts such that the subgraph induced by each part is connected, and the partition is maximally balanced in the way that the maximum cardinality of these k parts is minimized. We refer this problem to as min-max balanced connected graph partition into k parts and denote it as k-BGP. The vertex-weighted version of this problem on trees has been studied since about four decades ago, which admits a linear time exact algorithm. The vertex-weighted 2-BGP and 3-BGP admit a 5/4-approximation and a 3/2-approximation, respectively. When k ≥ 4 , no approximability result exists for k-BGP, i.e., the vertex unweighted variant, except a trivial k-approximation. In this paper, we present another 3/2-approximation for the 3-BGP and then extend it to become a k/2-approximation for k-BGP, for any fixed k ≥ 3 . Furthermore, for 4-BGP, we propose an improved 24/13-approximation. To these purposes, we have designed several local improvement operations, which could find more applications in related graph partition problems. [ABSTRACT FROM AUTHOR]

We consider a communication scheduling problem that arises within wireless sensor networks, where data is accumulated by the sensors and transferred directly to a central base station. One may choose to compress the data collected by a sensor, to decrease the data size for transmission, but the cost of compression must be considered. The goal is to designate a subset of sensors to compress their collected data, and then to determine a data transmission order for all the sensors, such that the total compression cost is minimized subject to a bounded data transmission completion time (a.k.a. makespan). A recent result confirms the NP-hardness for this problem, even in the special case where data compression is free. Here we first design a pseudo-polynomial time exact algorithm, articulated within a dynamic programming scheme. This algorithm also solves a variant with the complementary optimization goal—to minimize the makespan while constraining the total compression cost within a given budget. Our second result consists of a bi-factor (1+ϵ,2)-approximation for the problem, where (1+ϵ) refers to the compression cost and 2 refers to the makespan, and a 2-approximation for the variant. Lastly, we apply a sparsing technique to the dynamic programming exact algorithm, to achieve a dual fully polynomial time approximation scheme for the problem and a usual fully polynomial time approximation scheme for the variant. [ABSTRACT FROM AUTHOR]