A 6.55 factor primal-dual approximation algorithm for the connected facility location problem

In the connected facility location (ConFL) problem, we are given a graph G=(V,E) with nonnegative edge cost c _e on the edges, a set of facilities ??V, a set of demands (i.e., clients) $\mathcal{D}\subseteq VIn the connected facility location (ConFL) problem, we are given a graph G=(V,E) with nonnegative edge cost c _e on the edges, a set of facilities ℱ⊆V, a set of demands (i.e., clients) D í V\mathcal{D}\subseteq V , and a parameter M≥1. Each facility i has a nonnegative opening cost f _i and each client j has d _j units of demand. Our objective is to open some facilities, say F⊆ℱ, assign each demand j to some open facility i(j)∈F and connect all open facilities using a Steiner tree T such that the total cost, which is ?_{i ? F}f_i+?_{j ? D}d_jc_i(j)j+M?_{e ? T}c_e\sum_{i\in F}f_{i}+\sum_{j\in \mathcal{D}}d_{j}c_{i(j)j}+M\sum_{e\in T}c_{e} , is minimized. We present a primal-dual 6.55-approximation algorithm for the ConFL problem which improves the previous primal-dual 8.55-approximation algorithm given by Swamy and Kumar (Algorithmica 40:245–269, 2004).     

On domination number of Cartesian product of directed paths

Let γ(G) denote the domination number of a digraph G and let P _m □P _n denote the Cartesian product of P _m and P _n , the directed paths of length m and n. In this paper, we give a lower and upper bound for γ(P _m □P _n ). Furthermore, we obtain a necessary and sufficient condition for P _m □P _n to have efficient dominating set, and determine the exact values: γ(P ₂□P _n )=n, g(P₃\square P_n)=n+é\fracn4ù\gamma(P_{3}\square P_{n})=n+\lceil\frac{n}{4}\rceil, g(P₄\square P_n)=n+é\frac2n3ù\gamma(P_{4}\square P_{n})=n+\lceil\frac{2n}{3}\rceil, γ(P ₅□P _n )=2n+1 and g(P₆\square P_n)=2n+é\fracn+23ù\gamma(P_{6}\square P_{n})=2n+\lceil\frac{n+2}{3}\rceil.     

Capacity inverse minimum cost flow problem

Given a directed graph G=(N,A) with arc capacities u _ij and a minimum cost flow problem defined on G, the capacity inverse minimum cost flow problem is to find a new capacity vector [^(u)]\hat{u} for the arc set A such that a given feasible flow [^(x)]\hat{x} is optimal with respect to the modified capacities. Among all capacity vectors [^(u)]\hat{u} satisfying this condition, we would like to find one with minimum ||[^(u)]-u||\|\hat{u}-u\| value. We consider two distance measures for ||[^(u)]-u||\|\hat{u}-u\| , rectilinear (L ₁) and Chebyshev (L _∞) distances. By reduction from the feedback arc set problem we show that the capacity inverse minimum cost flow problem is NP\mathcal{NP} -hard in the rectilinear case. On the other hand, it is polynomially solvable by a greedy algorithm for the Chebyshev norm. In the latter case we propose a heuristic for the bicriteria problem, where we minimize among all optimal solutions the number of affected arcs. We also present computational results for this heuristic.     

The max quasi-independent set problem

In this paper, we deal with the problem of finding quasi-independent sets in graphs. This problem is formally defined in three versions, which are shown to be polynomially equivalent. The one that looks most general, namely, f-max quasi-independent set, consists of, given a graph and a non-decreasing function f, finding a maximum size subset Q of the vertices of the graph, such that the number of edges in the induced subgraph is less than or equal to f(|Q|). For this problem, we show an exact solution method that runs within time O^*(2^{\fracd-27/23d+1n})O^{*}(2^{\frac{d-27/23}{d+1}n}) on graphs of average degree bounded by d. For the most specifically defined γ-max quasi-independent set and k-max quasi-independent set problems, several results on complexity and approximation are shown, and greedy algorithms are proposed, analyzed and tested.     

Pooling designs associated with unitary space and ratio efficiency comparison

Let \mathbbF^(2n+d)_q²\mathbb{F}^{(2\nu+\delta)}_{q^{2}} be a (2ν+δ)-dimensional unitary space of \mathbbF_q²\mathbb{F}_{q^{2}} , where δ=0 or 1. In this paper we construct a family of inclusion matrices associated with subspaces of \mathbbF^(2n+d)_q²\mathbb{F}^{(2\nu+\delta)}_{q^{2}} , and exhibit its disjunct property. Moreover, we compare the ratio efficiency of this construction with others, and find it smaller under some conditions.     

Node-weighted Steiner tree approximation in unit disk graphs

Given a graph G=(V,E) with node weight w:V→R ⁺ and a subset S⊆V, find a minimum total weight tree interconnecting all nodes in S. This is the node-weighted Steiner tree problem which will be studied in this paper. In general, this problem is NP-hard and cannot be approximated by a polynomial time algorithm with performance ratio aln n for any 0<a<1 unless NP⊆DTIME(n ^O(log n)), where n is the number of nodes in s. In this paper, we are the first to show that even though for unit disk graphs, the problem is still NP-hard and it has a polynomial time constant approximation. We present a 2.5ρ-approximation where ρ is the best known performance ratio for polynomial time approximation of classical Steiner minimum tree problem in graphs. As a corollary, we obtain that there is a polynomial time (9.875+ε)-approximation algorithm for minimum weight connected dominating set in unit disk graphs, and also there is a polynomial time (4.875+ε)-approximation algorithm for minimum weight connected vertex cover in unit disk graphs.     

PTAS for minimum weighted connected vertex cover problem with <Emphasis Type="Italic">c</Emphasis>-local condition in unit disk graphs

Given a graph G=(V,E) with node weight w:V→R ⁺, the minimum weighted connected vertex cover problem (MWCVC) is to seek a subset of vertices of the graph with minimum total weight, such that for any edge of the graph, at least one endpoint of the edge is contained in the subset, and the subgraph induced by this subset is connected. In this paper, we study the problem on unit disk graph. A polynomial-time approximation scheme (PTAS) for MWCVC is presented under the condition that the graph is c-local.     

Domination in graphs with bounded propagation: algorithms,formulations and hardness results

We introduce a hierarchy of problems between the Dominating Set problem and the Power Dominating Set (PDS) problem called the ℓ-round power dominating set (ℓ-round PDS, for short) problem. For ℓ=1, this is the Dominating Set problem, and for ℓ≥n−1, this is the PDS problem; here n denotes the number of nodes in the input graph. In PDS the goal is to find a minimum size set of nodes S that power dominates all the nodes, where a node v is power dominated if (1) v is in S or it has a neighbor in S, or (2) v has a neighbor u such that u and all of its neighbors except v are power dominated. Note that rule (1) is the same as for the Dominating Set problem, and that rule (2) is a type of propagation rule that applies iteratively. The ℓ-round PDS problem has the same set of rules as PDS, except we apply rule (2) in “parallel” in at most ℓ−1 rounds. We prove that ℓ-round PDS cannot be approximated better than 2^log1-en2^{\log^{1-\epsilon}{n}} even for ℓ=4 in general graphs. We provide a dynamic programming algorithm to solve ℓ-round PDS optimally in polynomial time on graphs of bounded tree-width. We present a PTAS (polynomial time approximation scheme) for ℓ-round PDS on planar graphs for l = O(\fraclognloglogn)\ell=O(\frac{\log{n}}{\log{\log{n}}}) . Finally, we give integer programming formulations for ℓ-round PDS.     

Group testing in graphs

This paper studies the group testing problem in graphs as follows. Given a graph G=(V,E), determine the minimum number t(G) such that t(G) tests are sufficient to identify an unknown edge e with each test specifies a subset X⊆V and answers whether the unknown edge e is in G[X] or not. Damaschke proved that ⌈log ₂ e(G)⌉≤t(G)≤⌈log ₂ e(G)⌉+1 for any graph G, where e(G) is the number of edges of G. While there are infinitely many complete graphs that attain the upper bound, it was conjectured by Chang and Hwang that the lower bound is attained by all bipartite graphs. Later, they proved that the conjecture is true for complete bipartite graphs. Chang and Juan verified the conjecture for bipartite graphs G with e(G)≤2⁴ or for k≥5. This paper proves the conjecture for bipartite graphs G with e(G)≤2⁵ or for k≥6. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. J.S.-t.J. is supported in part by the National Science Council under grant NSC89-2218-E-260-013. G.J.C. is supported in part by the National Science Council under grant NSC93-2213-E002-28. Taida Institute for Mathematical Sciences, National Taiwan University, Taipei 10617, Taiwan. National Center for Theoretical Sciences, Taipei Office.     

Two constructions of new error-correcting pooling designs from orthogonal spaces over a finite field of characteristic 2

In this paper, we construct two classes of t×n,s ^e -disjunct matrix with subspaces in orthogonal space \mathbbF_q⁽²ⁿ⁺¹⁾\mathbb{F}_{q}^{(2\nu+1)} of characteristic 2 and exhibit their disjunct properties. We also prove that the test efficiency t/n of constructions II is smaller than that of D’yachkov et al. (J. Comput. Biol. 12:1129–1136, 2005).     

Bounded information dissemination in multi-channel wireless networks

More and more wireless networks and devices now operate on multiple channels, which poses the question: How to use multiple channels to speed up communication? In this paper, we answer this question for the case of wireless ad-hoc networks where information dissemination is a primitive operation. Specifically, we propose a randomized distributed algorithm for information dissemination that is very near the optimal. The general information dissemination problem is to deliver \(k\) information packets, stored initially in \(k\) different nodes (the packet holders), to all the nodes in the network, and the objective is to minimize the time needed. With an eye toward the reality, we assume a model where the packet holders are determined by an adversary, and neither the number \(k\) nor the identities of packet holders are known to the nodes in advance. Not knowing the value of \(k\) sets this problem apart from broadcasting and all-to-all communication (gossiping). We study the information dissemination problem in single-hop networks with bounded-size messages. We present a randomized algorithm which can disseminate all packets in \(O(k(\frac{1}{\mathcal {F}}+\frac{1}{\mathcal {P}})+\log ^2n)\) rounds with high probability, where \(\mathcal {F}\) is the number of available channels and \(\mathcal {P}\) is the bound on the number of packets a message can carry. Compared with the lower bound \(\varOmega (k(\frac{1}{\mathcal {F}}+\frac{1}{\mathcal {P}}))\), the given algorithm is very close to the asymptotical optimal except for an additive factor. Our result provides the first solid evidence that multiple channels can indeed substantially speed up information dissemination, which also breaks the \(\varOmega (k)\) lower bound that holds for single-channel networks (even if \(\mathcal {P}\) is infinity).     

A parameterized perspective on packing paths of length two

We study (vertex-disjoint) packings of paths of length two (i.e., of P ₂’s) in graphs under a parameterized perspective. Starting from a maximal P ₂-packing ℘ of size j we use extremal combinatorial arguments for determining how many vertices of ℘ appear in some P ₂-packing of size (j+1) (if such a packing exists). We prove that one can ‘reuse’ 2.5j vertices. We also show that this bound is asymptotically sharp. Based on a WIN-WIN approach, we build an algorithm which decides, given a graph, if a P ₂-packing of size at least k exists in time O^*(2.448^3k)\mathcal{O}^{*}(2.448^{3k}) .     

Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs

In this paper, we study the parameterized complexity of Dominating Set problem in chordal graphs and near chordal graphs. We show the problem is W[2]-hard and cannot be solved in time n ^o(k) in chordal and s-chordal (s>3) graphs unless W[1]=FPT. In addition, we obtain inapproximability results for computing a minimum dominating set in chordal and near chordal graphs. Our results prove that unless NP=P, the minimum dominating set in a chordal or s-chordal (s>3) graph cannot be approximated within a ratio of \fracc3lnn\frac{c}{3}\ln{n} in polynomial time, where n is the number of vertices in the graph and 0<c<1 is the constant from the inapproximability of the minimum dominating set in general graphs. In other words, our results suggest that restricting to chordal or s-chordal graphs can improve the approximation ratio by no more than a factor of 3. We then extend our techniques to find similar results for the Independent Dominating Set problem and the Connected Dominating Set problem in chordal or near chordal graphs.     

Approximation algorithms and hardness results for labeled connectivity problems

Let G=(V,E) be a connected multigraph, whose edges are associated with labels specified by an integer-valued function ℒ:E→ℕ. In addition, each label ℓ∈ℕ has a non-negative cost c(ℓ). The minimum label spanning tree problem (MinLST) asks to find a spanning tree in G that minimizes the overall cost of the labels used by its edges. Equivalently, we aim at finding a minimum cost subset of labels I⊆ℕ such that the edge set {e∈E:ℒ(e)∈I} forms a connected subgraph spanning all vertices. Similarly, in the minimum label s – t path problem (MinLP) the goal is to identify an s–t path minimizing the combined cost of its labels. The main contributions of this paper are improved approximation algorithms and hardness results for MinLST and MinLP.     

Just-in-time scheduling with controllable processing times on parallel machines

We study scheduling problems with controllable processing times on parallel machines. Our objectives are to maximize the weighted number of jobs that are completed exactly at their due date and to minimize the total resource allocation cost. We consider four different models for treating the two criteria. We prove that three of these problems are NP\mathcal{NP} -hard even on a single machine, but somewhat surprisingly, the problem of maximizing an integrated objective function can be solved in polynomial time even for the general case of a fixed number of unrelated parallel machines. For the three NP\mathcal{NP} -hard versions of the problem, with a fixed number of machines and a discrete resource type, we provide a pseudo-polynomial time optimization algorithm, which is converted to a fully polynomial time approximation scheme.     

A {{10}}-Approximation Algorithm for a Generalization of the Weighted Edge-Dominating Set Problem

We study the approximability of the weighted edge-dominating set problem. Although even the unweighted case is NP-Complete, in this case a solution of size at most twice the minimum can be efficiently computed due to its close relationship with minimum maximal matching; however, in the weighted case such a nice relationship is not known to exist. In this paper, after showing that weighted edge domination is as hard to approximate as the well studied weighted vertex cover problem, we consider a natural strategy, reducing edge-dominating set to edge cover. Our main result is a simple -approximation algorithm for the weighted edge-dominating set problem, improving the existing ratio, due to a simple reduction to weighted vertex cover, of 2r _WVC, where r _WVC is the approximation guarantee of any polynomial-time weighted vertex cover algorithm. The best value of r _WVC currently stands at . Furthermore we establish that the factor of is tight in the sense that it coincides with the integrality gap incurred by a natural linear programming relaxation of the problem.     

Tight bound for matching

Let M be the number of edges in a maximum matching in graphs with m edges, maximum vertex degree k and shortest simple odd-length cycle length L. We show that

Performance ratios of the Karmarkar-Karp differencing method

We consider the multiprocessor scheduling problem in which one must schedule n independent tasks nonpreemptively on m identical, parallel machines, such that the completion time of the last task is minimal. For this well-studied problem the Largest Differencing Method of Karmarkar and Karp outperforms other existing polynomial-time approximation algorithms from an average-case perspective. For m ≥ 3 the worst-case performance of the Largest Differencing Method has remained a challenging open problem. In this paper we show that the worst-case performance ratio is bounded between . For fixed m we establish further refined bounds in terms of n.     

A better constant-factor approximation for weighted dominating set in unit disk graph

This paper presents a (10+ε)-approximation algorithm to compute minimum-weight connected dominating set (MWCDS) in unit disk graph. MWCDS is to select a vertex subset with minimum weight for a given unit disk graph, such that each vertex of the graph is contained in this subset or has a neighbor in this subset. Besides, the subgraph induced by this vertex subset is connected. Our algorithm is composed of two phases: the first phase computes a dominating set, which has approximation ratio 6+ε (ε is an arbitrary positive number), while the second phase connects the dominating sets computed in the first phase, which has approximation ratio 4. This work is supported in part by National Science Foundation under grant CCF-9208913 and CCF-0728851; and also supported by NSFC (60603003) and XJEDU.     

On Ring Grooming in optical networks

An instance I of Ring Grooming consists of m sets A ₁,A ₂,…, A _m from the universe {0, 1,…, n − 1} and an integer g ≥ 2. The unrestricted variant of Ring Grooming, referred to as Unrestricted Ring Grooming, seeks a partition {P ₁ , P ₂, …,P _k } of {1, 2, …, m} such that for each 1 ≤ i ≤ k and is minimized. The restricted variant of Ring Grooming, referred to as Restricted Ring Grooming, seeks a partition of {1,2,…,m} such that | P _i | ≤ g for each and is minimized. If g = 2, we provide an optimal polynomial-time algorithm for both variants. If g > 2, we prove that both both variants are NP-hard even with fixed g. When g is a power of two, we propose an approximation algorithm called iterative matching. Its approximation ratio is exactly 1.5 when g = 4, at most 2.5 when g = 8, and at most in general while it is conjectured to be at most . The iterative matching algorithm is also extended for Unrestricted Ring Grooming with arbitrary g, and a loose upper bound on its approximation ratio is . In addition, set-cover based approximation algorithms have been proposed for both Unrestricted Ring Grooming and Restricted Ring Grooming. They have approximation ratios of at most 1 + log g, but running time in polynomial of m ^g . Work supported by a DIMACS postdoctoral fellowship.