A unified dual-fitting approximation algorithm for the facility location problems with linear/submodular penalties

In this paper, we study two variants of the classical facility location problem, namely, the facility location problem with linear penalties (FLPLP) and the facility location problem with submodular penalties (FLPSP), respectively. We give a unified dual-fitting based approximation algorithm for these two problems, yielding approximation ratios 2 and 3 respectively.     

Efficient Job Scheduling Algorithms with Multi-Type Contentions

In this paper, we consider an interesting generalization of the classic job scheduling problem in which each job needs to compete not only for machines but also for other types of resources. The contentions among jobs for machines and for resources could interfere with each other, which complicates the problem dramatically. We present a family of approximation algorithms for solving several variants of the problem by using a generic algorithmic framework. Our algorithms achieve a constant approximation ratio (i.e., 3) when there is only one type of resources or certain dependency relation exists among multiple types of resources. When the r resources are unrelated, the approximation ratio of our algorithm becomes k+2, where k≤ r is a constant depending on the problem instance. As an application, we also show that our techniques can be easily applied to optical burst switching (OBS) networks to design more efficient wavelength scheduling algorithms.This research was supported in part by an IBM faculty partnership award, and an IRCAF award from SUNY Buffalo.     

An approximation algorithm for maximum internal spanning tree

Given a graph G, the maximum internal spanning tree problem (MIST for short) asks for computing a spanning tree T of G such that the number of internal vertices in T is maximized. MIST has possible applications in the design of cost-efficient communication networks and water supply networks and hence has been extensively studied in the literature. MIST is NP-hard and hence a number of polynomial-time approximation algorithms have been designed for MIST in the literature. The previously best polynomial-time approximation algorithm for MIST achieves a ratio of \(\frac{3}{4}\). In this paper, we first design a simpler algorithm that achieves the same ratio and the same time complexity as the previous best. We then refine the algorithm into a new approximation algorithm that achieves a better ratio (namely, \(\frac{13}{17}\)) with the same time complexity. Our new algorithm explores much deeper structure of the problem than the previous best. The discovered structure may be used to design even better approximation or parameterized algorithms for the problem in the future.     

Performance of Selected Part-Machine Grouping Techniques for Data Sets of Wide Ranging Sizes and Imperfection

This study addresses the part-machine grouping problem in group technology, and evaluates die performance of several cell formation methods for a wide range of data set sizes. Algorithms belonging to four classes are evaluated: (1) array-based methods: bond energy algorithm (BEA), direct clustering analysis (DCA) and improved rank order clustering algorithm (ROC2); (2) non-hierarchical clustering method: ZODIAC; (3) augmented machine matrix methods: augmented p-median method (APM) and augmented linear clustering algorithm (ALC); and (4) neural network algorithms: ART1 and variants: ART1/KS, ART1/KSC, and Fuzzy ART. The experimental design is based on a mixture-model approach, utilizing replicated clustering. The performance measures include Rand Index and bond energy recovery ratio, as well as computational requirements for various algorithms. Experimental factors include problem size, degree of data imperfection, and algorithm tested. The results show that, among the algorithms applicable for large, industry-size data sets, ALC and neural networks are superior to ZODIAC, which in turn is generally superior to array-based methods of ROC2 and DCA.     

A novel approach for detecting multiple rumor sources in networks with partial observations

Locating source of information diffusion in networks has very important applications such as locating the sources of epidemics, news/rumors in social networks or online computer virus. In this paper, we consider detecting multiple rumor sources from a deterministic point of view by modeling it as the set resolving set (SRS) problem. Let G be a network on n nodes. A node subset K is an SRS of G if all detectable node sets are distinguishable by K. The problem of multiple rumor source detection (MRSD) in the network can be modeled as finding an SRS K with the smallest cardinality. In this paper, we propose a polynomial-time greedy algorithm for finding a minimum SRS in a general network, achieving performance ratio \(O(\ln n)\). This is the first work establishing a relation between the MRSD problem and a deterministic concept of SRS, and a first work to give the minimum SRS problem a polynomial-time performance-guaranteed approximation algorithm. Our framework suggests a robust and efficient approach for estimating multiple rumor sources independent of diffusion models in networks.     

Packing trees in communication networks

Given an undirected edge-capacitated graph and given (possibly) different subsets of vertices, we consider the problem of selecting a maximum (weighted) set of Steiner trees, each tree spanning a subset of vertices, without violating the capacity constraints. This problem is motivated by applications in multicast communication networks. We give an integer linear programming (ILP) formulation for the problem, and observe that its linear programming (LP) relaxation is a fractional packing problem with exponentially many variables and a block (sub-)problem that cannot be solved in polynomial time. To this end, we take an r-approximate block solver (a weak block solver) to develop a (1−ε)/r-approximation algorithm for the LP relaxation. The algorithm has a polynomial coordination complexity for any ε∈(0,1). To the best of our knowledge, this is the first approximation result for fractional packing problems with only weak block solvers (with arbitrarily large approximation ratio) and a coordination complexity that is polynomial in the input size. This leads also to an approximation algorithm for the underlying tree packing problem. Finally, we extend our results to an important multicast routing and wavelength assignment problem in optical networks, where each Steiner tree is to be assigned one of a limited set of given wavelengths, so that trees crossing the same fiber are assigned different wavelengths. A preliminary version of this paper appeared in the Proceedings of the 1st Workshop on Internet and Network Economics (WINE 2005), LNCS, vol. 3828, pp. 688–697. Research supported by a MITACS grant for all the authors, an NSERC post doctoral fellowship for the first author, the NSERC Discovery Grant #5-48923 for the second and fourth author, NSERC Discovery Grant #15296 for the third author, the Canada Research Chair Program for the second author, and an NSERC industrial and development fellowship for the fourth author.     

Single machine scheduling with non-availability interval and optional job rejection

This paper studies the single machine scheduling problem with availability constraints and optional job rejection. We consider the non-resumable and resumable variants, and show that the problems remain ordinary NP-hard, even with the rejection possibility extension, by presenting pseudo-polynomial dynamic-programming (DP) solutions. We also present an enhanced running time implementation of the algorithm of Kellerer and Strusevich (Algorithmica 57(4):769–795, 2010) for the resumable scenario without job rejection. This solution is adapted to efficiently solve the machine non-availability problem with a floating interval and the problem of two competing agents on a single machine, with and without optional job rejection. Numerical experiments support the efficiency of our DP implementation.

     

Clustering Binary Oligonucleotide Fingerprint Vectors for DNA Clone Classification Analysis

We considered the problem of clustering binarized oligonucleotide fingerprints that attempts to identify clusters. Oligonucleotide fingerprinting is a powerful DNA array based method to characterize cDNA and rRNA libraries and has many applications including gene expression profiling and DNA clone classification. DNA clone classification is the main application for the problem considered in this paper. Most of the existing approaches for clustering use normalized real intensity values and thus do not treat positive and negative hybridization signals equally. This is demonstrated in a series of recent publications where a discrete approach typically useful in the classification of microbial rRNA clones has been proposed. In the discrete approach, hybridization intensities are normalized and thresholds are set such that a value of 1 represents hybridization, a value of 0 represents no hybridization, and an N represents unknown, which is also called a missing value. A combinatorial optimization problem is then formulated attempting to cluster the fingerprints and resolve the missing values simultaneously. It has been examined that missing values cause much difficulty in clustering analysis and most clustering methods are very sensitive to them. In this paper, we turned a little back to the traditional clustering problem, which takes in no missing values but with the revised goal to stabilize the number of clusters and maintain the clustering quality. We adopted the binarizing scheme used in the discrete approach as it is shown to be typically useful for the clone classifications. We formulated such a problem into another combinatorial optimization problem. The computational complexity of this new clustering problem and its relationships to the discrete approach and the traditional clustering problem were studied. We have designed an exact algorithm for the new clustering problem, which is an A* search algorithm for finding a minimum number of clusters. The experimental results on two commonly tested real datasets demonstrated that the A* search algorithm runs fast and performs better than some popular hierarchical clustering methods, in terms of separating clones that have different characteristics with respect to the given oligonucleotide probes.Supported by NSERC and CFI.Supported by NSERC.Supported partially by NSERC, CFI, and NNSF Grant 60373012.     

On recovering syntenic blocks from comparative maps

A genomic map is represented by a sequence of gene markers, and a gene marker can appear in several different genomic maps, in either positive or negative form. A strip (syntenic block) is a sequence of distinct markers that appears as subsequences in two or more maps, either directly or in reversed and negated form. Given two genomic maps G and H, the problem Maximal Strip Recovery (MSR) is to find two subsequences G′ and H′ of G and H, respectively, such that the total length of disjoint strips in G′ and H′ is maximized. Previously only a heuristic was provided for this problem, which does not guarantee finding the optimal solution, and it was unknown whether the problem is NP-hard or polynomially solvable. In this paper, we develop a factor-4 polynomial-time approximation algorithm for the problem, and show that several close variants of the problem are intractable.     

Approximation algorithms for multicast routing in ad hoc wireless networks

Energy efficient multicast problem is one of important issues in ad hoc networks. In this paper, we address the energy efficient multicast problem for discrete power levels in ad hoc wireless networks. The problem of our concern is: given n nodes deployed over 2-D plane and each node v has l(v) transmission power levels and a multicast request (s,D) (clearly, when D is V∖{s}, the multicast request is a broadcast request), how to find a multicast tree rooted at s and spanning all destinations in D such that the total energy cost of the multicast tree is minimized. We first prove that this problem is NP-hard and it is unlikely to have an approximation algorithm with performance ratio ρlnn(ρ<1). Then, we propose a general algorithm for the multicast/broadcast tree problem. And based on the general algorithm, we propose an approximation algorithm and a heuristics for multicast tree problem. Especially, we also propose an efficient heuristic for broadcast tree problem. Simulations ensure our algorithms are efficient.     

On minimum <Emphasis Type="Italic">m</Emphasis>-connected <Emphasis Type="Italic">k</Emphasis>-dominating set problem in unit disc graphs

Minimum m-connected k-dominating set problem is as follows: Given a graph G=(V,E) and two natural numbers m and k, find a subset S⊆V of minimal size such that every vertex in V∖S is adjacent to at least k vertices in S and the induced graph of S is m-connected. In this paper we study this problem with unit disc graphs and small m, which is motivated by the design of fault-tolerant virtual backbone for wireless sensor networks. We propose two approximation algorithms with constant performance ratios for m≤2. We also discuss how to design approximation algorithms for the problem with arbitrarily large m. This work was supported in part by the Research Grants Council of Hong Kong under Grant No. CityU 1165/04E, the National Natural Science Foundation of China under Grant No. 70221001, 10531070 and 10771209.     

Single-machine scheduling problems with general truncated sum-of-actual-processing-time-based learning effect

We study single machine scheduling problems with general truncated sum-of-actual-processing-time-based learning effect. In the general truncated learning model, the actual processing time of a job is affected by the sum of actual processing times of previous jobs and by a job-dependent truncation parameter. We show that the single machine problems to minimize makespan and to minimize the sum of weighted completion times are both at least ordinary NP-hard and the single machine problem to minimize maximum lateness is strongly NP-hard. We then show polynomial solvable cases and approximation algorithms for these problems. Computational experiments are also conducted to show the effectiveness of our approximation algorithms.

     

A self-stabilizing 3-approximation for the maximum leaf spanning tree problem in arbitrary networks

The maximum leaf spanning tree (MLST) is a good candidate for constructing a virtual backbone in self-organized multihop wireless networks, but is practically intractable (NP-complete). Self-stabilization is a general technique that permits to recover from catastrophic transient failures in self-organized networks without human intervention. We propose a fully distributed self-stabilizing approximation algorithm for the MLST problem in arbitrary topology networks. Our algorithm is the first self-stabilizing protocol that is specifically designed to approximate an MLST. It builds a solution whose number of leaves is at least 1/3 of the maximum possible in arbitrary graphs. The time complexity of our algorithm is O(n ²) rounds.     

New algorithms for k-center and extensions

The problem of interest is covering a given point set with homothetic copies of several convex containers C ₁,…,C _k , while the objective is to minimize the maximum over the dilatation factors. Such k-containment problems arise in various applications, e.g. in facility location, shape fitting, data classification or clustering. So far most attention has been paid to the special case of the Euclidean k-center problem, where all containers C _i are Euclidean unit balls. Recent developments based on so-called core-sets enable not only better theoretical bounds in the running time of approximation algorithms but also improvements in practically solvable input sizes. Here, we present some new geometric inequalities and a Mixed-Integer-Convex-Programming formulation. Both are used in a very effective branch-and-bound routine which not only improves on best known running times in the Euclidean case but also handles general and even different containers among the C _i .     

Multimodal hub location and hub network design

Through observations from real life hub networks, we introduce the multimodal hub location and hub network design problem. We approach the hub location problem from a network design perspective. In addition to the location and allocation decisions, we also study the decision on how the hub networks with different possible transportation modes must be designed. In this multimodal hub location and hub network design problem, we jointly consider transportation costs and travel times, which are studied separately in most hub location problems presented in the literature. We allow different transportation modes between hubs and different types of service time promises between origin–destination pairs while designing the hub network in the multimodal problem. We first propose a linear mixed integer programming model for this problem and then derive variants of the problem that might arise in certain applications. The models are enhanced via a set of effective valid inequalities and an efficient heuristic is developed. Computational analyses are presented on the various instances from the Turkish network and CAB data set.     

An approximation algorithm for the balanced Max-3-Uncut problem using complex semidefinite programming rounding

Graph partition problems have been investigated extensively in combinatorial optimization. In this work, we consider an important graph partition problem which has applications in the design of VLSI circuits, namely, the balanced Max-3-Uncut problem. We formulate the problem as a discrete linear program with complex variables and propose an approximation algorithm with an approximation ratio of 0.3456 using a semidefinite programming rounding technique along with a greedy swapping step afterwards to guarantee the balanced constraint. Our analysis utilizes a bivariate function, rather than the univariate function in previous work.     

Constructing weakly connected dominating set for?secure clustering in distributed sensor network

Secure clustering problem plays an important role in distributed sensor networks. Weakly Connected Dominating Set (WCDS) is used for solving this problem. Therefore, computing a minimum WCDS becomes an important topic of this research. In this paper, we compare the size of Maximal Independent Set (MIS) and minimum WCDS in unit disk graph. Our analysis shows that five is the least upper bound for this ratio. We also present a distributed algorithm to produce a weakly connected MIS within a factor 5 from the minimum WCDS.     

Polynomial time approximation schemes for minimum disk cover problems

The following planar minimum disk cover problem is considered in this paper: given a set D\mathcal{D} of n disks and a set ℘ of m points in the Euclidean plane, where each disk covers a subset of points in ℘, to compute a subset of disks with minimum cardinality covering ℘. This problem is known to be NP-hard and an algorithm which approximates the optimal disk cover within a factor of (1+ε) in O(mn^{O(\frac1e2log2\frac1e)})\mathcal{O}(mn^{\mathcal{O}(\frac{1}{\epsilon^{2}}\log^{2}\frac{1}{\epsilon})}) time is proposed in this paper. This work presents the first polynomial time approximation scheme for the minimum disk cover problem where the best known algorithm can approximate the optimal solution with a large constant factor. Further, several variants of the minimum disk cover problem such as the incongruent disk cover problem and the weighted disk cover problem are considered and approximation schemes are designed.     

DYNAMIC FEEDING IN A STOCHASTIC PARALLEL PROCESSING SYSTEM

I consider a dynamic input scheduling problem of a stochastic parallel processing system consisting of n identical flexible machining cells. The processing times at each cell are independent random variables. Previous study has indicated the NP complexity of the problem. In this paper, I prove the separability under an ideal just-in-time input condition. Using the separability, I then construct an approximation procedure for most realistic applications where the separability condition is violated. The approximation procedure requires only linear time and performed quite well on an extensive test with numerical examples.     

Almost optimal solutions for bin coloring problems

In this paper we study two interesting bin coloring problems: Minimum Bin Coloring Problem (MinBC) and Online Maximum Bin Coloring Problem (OMaxBC), motivated from several applications in networking. For the MinBC problem, we present two near linear time approximation algorithms to achieve almost optimal solutions, i.e., no more than OPT+2 and OPT+1 respectively, where OPT is the optimal solution. For the OMaxBC problem, we first introduce a deterministic 2-competitive greedy algorithm, and then give lower bounds for any deterministic and randomized (against adaptive offline adversary) online algorithms. The lower bounds show that our deterministic algorithm achieves the best possible competitive ratio. The research of this paper was partially supported by an NSF CAREER award CCF-0546509.