Improved deterministic algorithms for weighted matching and packing problems

Based on the method of (n,k)-universal sets, we present a deterministic parameterized algorithm for the weighted rd-matching problem with time complexity O^∗(4^{(r−1)k+o(k)}), improving the previous best upper bound O^∗(4^rk+o(k)). In particular, the algorithm applied to the unweighted 3d-matching problem results in a deterministic algorithm with time O^∗(16^k+o(k)), improving the previous best result O^∗(21.26^k). For the weighted r-set packing problem, we present a deterministic parameterized algorithm with time complexity O^∗(2^{(2r−1)k+o(k)}), improving the previous best result O^∗(2^2rk+o(k)). The algorithm, when applied to the unweighted 3-set packing problem, has running time O^∗(32^k+o(k)), improving the previous best result O^∗(43.62^k+o(k)). Moreover, for the weighted r-set packing and weighted rd-matching problems, we give a kernel of size O(k^r), which is the first kernelization algorithm for the problems on weighted versions.     

Approximation algorithms for covering/packing integer programs

Given matrices A and B and vectors a, b, c and d, all with non-negative entries, we consider the problem of computing . We give a bicriteria-approximation algorithm that, given ε∈(0,1], finds a solution of cost O(ln(m)/ε²) times optimal, meeting the covering constraints (Ax?a) and multiplicity constraints (x?d), and satisfying Bx?(1+ε)b+β, where β is the vector of row sums β_i=∑_jB_ij. Here m denotes the number of rows of A.This gives an O(lnm)-approximation algorithm for CIP—minimum-cost covering integer programs with multiplicity constraints, i.e., the special case when there are no packing constraints Bx?b. The previous best approximation ratio has been O(ln(max_j∑_iA_ij)) since 1982. CIP contains the set cover problem as a special case, so O(lnm)-approximation is the best possible unless P=NP.     

Efficient heuristic algorithms for the weighted set covering problem

In this paper two heuristic algorithms are presented for the weighted set covering problem. The first algorithm uses a simple, polynomial procedure to construct feasible covering solutions. The procedure is shown to possess a worst case performance bound that is a function of the size of the problem. The second algorithm is a solution improvement procedure that attempts to form reduced cost composite solutions from available feasible covering solutions. Computational results are presented for both algorithms on several large set covering problems generated from airline crew scheduling data.     

Fuzzy logic based algorithms for maximum covering location problems

This paper concerns a class of maximum covering location problems in networks in uncertain environments. It is assumed that (a) relative weights of demand nodes are either deterministic or imprecise, described by linguistic expressions and (b) potential facility site locations are limited to network nodes. The concept of coverage is extended to include a degree of node coverage which means that the borders between the subset of covered demand nodes and the subset of uncovered demand nodes are inexact. The acceptable service distance/travelling times from a facility site to demand nodes are modelled by fuzzy sets. Three new algorithms for choosing the best facility locations are developed which assume that (1) demands at all nodes are equally important, (2) relative weights of demand at nodes are deterministic and (3) weights of demand at nodes are imprecise and described by linguistic terms, respectively. The algorithms are based on searching among potential facility nodes by applying comparison operations on discrete fuzzy sets. It is shown how to extend the proposed algorithms from one-site to multi-site covering problems. Illustrative examples of selecting locations for logistics centres in a distribution company are given.     

Bandwidth allocation algorithms for weighted maximum rate constrained link sharing policy

This paper addresses the problem of bandwidth allocation under the weighted maximum rate constrained link sharing policy and proves a key theory in the condition of allocation termination. We propose several algorithms with various worst-case and average-case time complexities, and evaluate their computation elapse times.     

On approximating four covering and packing problems

In this paper, we consider approximability issues of the following four problems: triangle packing, full sibling reconstruction, maximum profit coverage and 2-coverage. All of them are generalized or specialized versions of set-cover and have applications in biology ranging from full-sibling reconstructions in wild populations to biomolecular clusterings; however, as this paper shows, their approximability properties differ considerably. Our inapproximability constant for the triangle packing problem improves upon the previous results in [A. Caprara, R. Rizzi, Packing triangles in bounded degree graphs, Inform. Process. Lett. 84 (4) (2002) 175–180; J. Chlebíková, M. Chlebík, Complexity of approximating bounded variants of optimization problems, Theoret. Comput. Sci. 354 (3) (2006) 320–338]; this is done by directly transforming the inapproximability gap of Håstad for the problem of maximizing the number of satisfied equations for a set of equations over GF(2) [J. Håstad, Some optimal inapproximability results, in: Proc. of the 29th Annual ACM Symp. on Theory of Computing, 1997, pp. 1–10] and is interesting in its own right. Our approximability results on the full siblings reconstruction problems answers questions originally posed by Berger-Wolf et al. [T.Y. Berger-Wolf, B. DasGupta, W. Chaovalitwongse, M.V. Ashley, Combinatorial reconstruction of sibling relationships, in: Proc. of the 6th International Symposium on Computational Biology and Genome Informatics, 2005, pp. 1252–1255; T.Y. Berger-Wolf, S. Sheikh, B. DasGupta, M.V. Ashley, I. Caballero, W. Chaovalitwongse, S.L. Putrevu, Reconstructing sibling relationships in wild populations, Bioinformatics 23 (13) (2007) i49–i56] and our results on the maximum profit coverage problem provides almost matching upper and lower bounds on the approximation ratio, answering a question posed by Hassin and Or [R. Hassin, E. Or, A maximum profit coverage algorithm with application to small molecules cluster identification, in: 5th International Workshop Experimental Algorithms, in: Lecture Notes in Comput. Sci., vol. 4007, Springer-Verlag, 2006, pp. 265–276].     

Approximation algorithms for partially covering with edges

The edge dominating set (EDS) and edge-cover (EC) problems are classical graph covering problems in which one seeks a minimum cost collection of edges which covers the edges or vertices, respectively, of a graph. We consider the generalized partial cover version of these problems, in which failing to cover an edge, in the EDS case, or vertex, in the EC case, induces a penalty. Given a bound on the total amount of penalties that we are permitted to pay, the objective is to find a minimum cost cover with respect to this bound. We give an 8/3-approximation for generalized partial EDS. This result matches the best-known guarantee for the {0,1}-EDS problem, a specialization in which only a specified set of edges need to be covered. Moreover, 8/3 corresponds to the integrality gap of the natural formulation of the {0,1}-EDS problem. Our techniques can also be used to derive an approximation scheme for the generalized partial edge-cover problem, which is -complete even though the uniform penalty version of the partial edge-cover problem is in .     

Comparing online algorithms for bin packing problems

The relative worst-order ratio is a measure of the quality of online algorithms. In contrast to the competitive ratio, this measure compares two online algorithms directly instead of using an intermediate comparison with an optimal offline algorithm.     

Lower bounds for on-line two-dimensional packing algorithms

Summary Many problems, such as cutting stock problems and the scheduling of tasks with a shared resource, can be viewed as two-dimensional bin packing problems. Using the two-dimensional packing model of Baker, Coffman, and Rivest, a finite list L of rectangles is to be packed into a rectangular bin of finite width but infinite height, so as to minimize the total height used. An algorithm which packs the list in the order given without looking ahead or moving pieces already packed is called an on-line algorithm. Since the problem of finding an optimal packing is NP-hard, previous work has been directed at finding approximation algorithms. Most of the approximation algorithms which have been studied are on-line except that they require the list to have been previously sorted by height or width. This paper examines lower bounds for the worst-case performance of on-line algorithms for both non-preordered lists and for lists preordered by increasing or decreasing height or width.This author's work was supported by the Joint Services Electronics Program (U.S. Army, U.S. Navy and U.S. Air Force) under Contract DAAG-29-78-C-0016     

Approximation algorithms for orthogonal packing problems for hypercubes

Orthogonal packing problems are natural multidimensional generalizations of the classical bin packing problem and knapsack problem and occur in many different settings. The input consists of a set I={_r1,…,_rn}$I=\{r_1,\dots ,r_n\}$ of d$d$-dimensional rectangular items _ri=(_ai,1,…,_ai,d)$r_i=(a_{i,1},\dots ,a_{i,d})$ and a space Q$Q$. The task is to pack the items in an orthogonal and non-overlapping manner without using rotations into the given space. In the strip packing setting the space Q$Q$ is given by a strip of bounded basis and unlimited height. The objective is to pack all items into a strip of minimal height. In the knapsack packing setting the given space Q$Q$ is a single, usually unit sized bin and the items have associated profits _pi$p_i$. The goal is to maximize the profit of a selection of items that can be packed into the bin.     

Distributed algorithms for cooperative control

Expressing a cooperative control system requires combining tools from control theory and distributed computation. After reviewing several possible formalisms appropriate for the job, the authors settle on the computation and control language and illustrate its main features and advantages using a cooperative tracking task. We demonstrate some of the concepts involved in using a multirobot task. We also discuss CCL's ability to be a programming language as well as a modeling tool, which lets us directly simulate or execute CCL models.     

Branch-and-bound algorithm for the maximum triangle packing problem

This work addresses the problem of finding the maximum number of unweighted vertex-disjoint triangles in an undirected graph G. It is a challenging NP-hard combinatorial problem and it is well-known to be APX-hard. A branch-and-bound algorithm which uses a lower bound based on neighborhood degree is presented. A naive upper bound is proposed as well as another one based on a surrogate relaxation of the related integer linear program which is analogous to a multidimensional knapsack problem. Further, a Greedy Search algorithm and a genetic algorithm are described to improve the lower bound. A computational comparison of lower bounds, branch-and-bound algorithm and CPLEX solver is provided using randomly generated benchmarks and well-known DIMACS implementation challenges. The empirical study shows that the branch-and-bound finds the optimal triangle packing solution for small randomly generated MTP instances (up to 100 vertices and 200 triangles) and some DIMACS graphs. For some larger instances and DIMACS challenges graphs, we remark that our lower bound outperforms CPLEX solver regarding the triangle packing solution and the computation time.     

Intelligent-guided adaptive search for the maximum covering location problem

Computational intelligence techniques are part of the search process in several recent heuristics. One of their main benefits is the use of an adaptive memory to guide the search towards regions with promising solutions. This paper follows this approach proposing a variation of a well-known iteration independent metaheuristic. This variation adds a learning stage to the search process, which can improve the quality of the solutions found. The proposed metaheuristic, named Intelligent-Guided Adaptive Search (IGAS), provides an efficient solution to the maximum covering facility location problem. Computational experiments conducted by the authors showed that the solutions found by IGAS were better than the solutions obtained by popular methods found in the literature.