We study a capacitated network design problem with applications in local access network design. Given a network, the problem is to route flow from several sources to a sink and to install capacity on the edges to supp...
详细信息
We study a capacitated network design problem with applications in local access network design. Given a network, the problem is to route flow from several sources to a sink and to install capacity on the edges to support the flow at minimum cost. Capacity can be purchased only in multiples of a fixed quantity. All the flow from a source must be routed in a single path to the sink. This NP-hard problem generalizes the Steiner tree problem and also more effectively models the applications traditionally formulated as capacitated tree problems. We present an approximation algorithm with performance ratio (rho(ST) + 2) where rho(ST) is the performance ratio of any approximation algorithm for the minimum Steiner tree problem. When all sources have unit demand, the ratio improves to (rho(ST) + 1) and, in particular, to 2 when all nodes in the graph are sources.
The input to the METRIC MAXIMUM CLUSTERING PROBLEM WITH GIVEN CLUSTER SIZES consists of a complete graph G=(V, E) with edge weights satisfying the triangle inequality, and integers c(1),...., c(p) that sum to I V. The...
详细信息
The input to the METRIC MAXIMUM CLUSTERING PROBLEM WITH GIVEN CLUSTER SIZES consists of a complete graph G=(V, E) with edge weights satisfying the triangle inequality, and integers c(1),...., c(p) that sum to I V. The goal is to find a partition of V into disjoint clusters of sizes c(1),....,c(p), that maximizes the sum of weights of edges whose two ends belong to the same cluster. We describe approximation algorithms for this problem. (C) 2003 Elsevier Science B.V. All rights reserved.
Intensity modulated radiation therapy (IMRT) is one of the most effective modalities for modem cancer treatment. The key to successful IMRT treatment hinges on the delivery of a two-dimensional discrete radiation inte...
详细信息
Intensity modulated radiation therapy (IMRT) is one of the most effective modalities for modem cancer treatment. The key to successful IMRT treatment hinges on the delivery of a two-dimensional discrete radiation intensity matrix using a device called a multileaf collimator (MLC). Mathematically, the delivery of an intensity matrix using an MLC can be viewed as the problem of representing a non-negative integral matrix (i.e., the intensity matrix) by a linear combination of certain special non-negative integral matrices called segments, where each such segment corresponds to one of the allowed states of the MLC. The problem of representing the intensity matrix with the minimum number of segments is known to be NP-complete. In this paper, we present two approximation algorithms for this matrix representation problem. To the best of our knowledge, these are the first algorithms to achieve non-trivial performance guarantees for multi-row intensity matrices. (c) 2006 Elsevier B.V. All rights reserved.
Stochastic combinatorial optimization problems are usually defined as planning problems, which involve purchasing and allocating resources in order to meet uncertain needs. For example, network designers need to make ...
详细信息
Stochastic combinatorial optimization problems are usually defined as planning problems, which involve purchasing and allocating resources in order to meet uncertain needs. For example, network designers need to make their best guess about the future needs of the network and purchase capabilities accordingly. Facing uncertain in the future, we either "wait and see" changes, or postpone decisions about resource allocation until the requirements or constraints become realized. Specifically, in the field of stochastic combinatorial optimization, some inputs of the problems are uncertain, but follow known probability distributions. Our goal is to find a strategy that minimizes the expected cost. In this paper, we consider the two-stage finite-scenario stochastic set cover problem and the single sink rent-or-buy problem by presenting primal-dual based approximation algorithms for these two problems with approximation ratio 2 eta and 4.39, respectively, where eta is the maximum frequency of the element of the ground set in the set cover problem.
In a traditional classification problem, we wish to assign one of k labels (or classes) to each of n objects, in a way that is consistent with some observed data that we have about the problem. An active line of resea...
详细信息
In a traditional classification problem, we wish to assign one of k labels (or classes) to each of n objects, in a way that is consistent with some observed data that we have about the problem. An active line of research in this area is concerned with classification when one has information about pairwise relationships among the objects to be classified;this issue is one of the principal motivations for the framework of Markov random fields, and it arises in areas such as image processing, biometry, and document analysis. In its most basic form, this style of analysis seeks to find a classification that optimizes a combinatorial function consisting of assignment costs-based on the individual choice of label we make for each object-and separation costs-based on the pair of choices we make for two "related" objects. We formulate a general classification problem of this type, the metric labeling problem;we show that it contains as special cases a number of standard classification frameworks, including several arising from the theory of Markov random fields. From the perspective of combinatorial optimization, our problem can be viewed as a substantial generalization of the multiway cut problem, and equivalent to a type of uncapacitated quadratic assignment problem. We provide the first nontrivial polynomial-time approximation algorithms for a general family of classification problems of this type. Our main result is an O (log k log log k)-approximation algorithm for the metric labeling problem, with respect to an arbitrary metric on a set of k labels, and an arbitrary weighted graph of relationships on a set of objects. For the special case in which the labels are endowed with the uniform metric-all distances are the same-our methods provide a 2-approximation algorithm.
We consider the problem of constructing optimal decision trees: given a collection of tests that can disambiguate between a set of m possible diseases, each test having a cost, and the a priori likelihood of any parti...
详细信息
We consider the problem of constructing optimal decision trees: given a collection of tests that can disambiguate between a set of m possible diseases, each test having a cost, and the a priori likelihood of any particular disease, what is a good adaptive strategy to perform these tests to minimize the expected cost to identify the disease? This problem has been studied in several works, with O(log m)-approximations known in the special cases when either costs or probabilities are uniform. In this paper, we settle the approximability of the general problem by giving a tight O(log m)-approximation algorithm. We also consider a substantial generalization, the adaptive traveling salesman problem. Given an underlying metric space, a random subset S of vertices is drawn from a known distribution, but S is initially unknown-we get information about whether any vertex is in S only when it is visited. What is a good adaptive strategy to visit all vertices in the random subset S while minimizing the expected distance traveled? This problem has applications in routing message ferries in ad hoc networks and also models switching costs between tests in the optimal decision tree problem. We give a polylogarithmic approximation algorithm for adaptive TSP, which is nearly best possible due to a connection to the well-known group Steiner tree problem. Finally, we consider the related adaptive traveling repairman problem, where the goal is to compute an adaptive tour minimizing the expected sum of arrival times of vertices in the random subset S;we obtain a polylogarithmic approximation algorithm for this problem as well.
In this article we study a generalized team orienteering problem (GTOP), which is to find service paths for multiple homogeneous vehicles in a network such that the profit sum of serving the nodes in the paths is maxi...
详细信息
In this article we study a generalized team orienteering problem (GTOP), which is to find service paths for multiple homogeneous vehicles in a network such that the profit sum of serving the nodes in the paths is maximized, subject to the cost budget of each vehicle. This problem has many potential applications in IoTs and smart cities, such as dispatching energy-constrained mobile chargers to charge as many energy-critical sensors as possible to prolong the network lifetime. In this article, we first formulate the GTOP problem, where each node can be served by different vehicles, and the profit of serving the node is a submodular function of the number of vehicles serving it. We then propose a novel (1-(1/epsilon)1/2+epsilon)-approximation algorithm for the problem, where epsilon is a given constant with 0 < epsilon <= 1 and e is the base of the natural logarithm. In particular, the approximation ratio is about 0.33 when epsilon = 0.5. In addition, we devise an improved approximation algorithm for a special case of the problem where the profit is the same by serving a node once and multiple times. We finally evaluate the proposed algorithms with simulation experiments, and the results of which are very promising. Especially, the profit sums delivered by the proposed algorithms are up to 14% higher than those by existing algorithms, and about 93.6% of the optimal solutions.
In generalized tree alignment problem, we are given a set S of k biologically related sequences and we are interested in a minimum cost evolutionary tree for S. In many instances of this problem partial phylogenetic t...
详细信息
In generalized tree alignment problem, we are given a set S of k biologically related sequences and we are interested in a minimum cost evolutionary tree for S. In many instances of this problem partial phylogenetic tree for S is known. In such instances, we would like to make use of this knowledge to restrict the tree topologies that we consider and construct a biologically relevant minimum cost evolutionary tree. So, we propose the following natural generalization of the generalized tree alignment problem, a problem known to be MAX-SNP Hard, stated as follows: Constrained Generalized Tree Alignment Problem [S. Divakaran, algorithms and heuristics for constrained generalized alignment problem, DIMACS Technical Report 2007-21, 2007]: Given a set S of k related sequences and a phylogenetic forest comprising of node-disjoint phylogenetic trees that specify the topological constraints that an evolutionary tree of S needs to satisfy, construct a minimum cost evolutionary tree for S. In this paper, we present constant approximation algorithms for the constrained generalized tree alignment problem. For the generalized tree alignment problem, a special case of this problem, our algorithms provide a guaranteed error bound of 2 - 2/k. (C) 2009 Published by Elsevier B.V.
Broadcasting is a fundamental operation in wireless networks and plays an important role in the communication protocol design. In multihop wireless networks, however, interference at a node due to simultaneous transmi...
详细信息
Broadcasting is a fundamental operation in wireless networks and plays an important role in the communication protocol design. In multihop wireless networks, however, interference at a node due to simultaneous transmissions from its neighbors makes it nontrivial to design a minimum-latency broadcast algorithm, which is known to be NP-complete. We present a simple 12-approximation algorithm for the one-to-all broadcast problem that improves all previously known guarantees for this problem. We then consider the all-to-all broadcast problem where each node sends its own message to all other nodes. For the all-to-all broadcast problem, we present two algorithms with approximation ratios of 20 and 34, improving the best result available in the literature. Finally, we report experimental evaluation of our algorithms. Our studies indicate that our algorithms perform much better in practice than the worst-case guarantees provided in the theoretical analysis and achieve up to 37 percent performance improvement over existing schemes.
Given a single machine and a set of jobs with due dates, the classical NP-hard. problem of scheduling to minimize total tardiness is a well-understood one. Lawler gave a fully polynomial-time approximation scheme (FPT...
详细信息
Given a single machine and a set of jobs with due dates, the classical NP-hard. problem of scheduling to minimize total tardiness is a well-understood one. Lawler gave a fully polynomial-time approximation scheme (FPTAS) for it some 20 years ago. If the jobs have positive weights the problem of minimizing total weighted tardiness seems to be considerably more intricate. it. In this paper, we give some of the first approximation algorithms for it. We examine first the weighted problem with a fixed number of due dates and we design a pseudopolynomial algorithm for it. We show how to transform the pseudopolynomial algorithm to an FPTAS for the case where the weights are polynomially bounded. For the case with an arbitrary number of due dates and polynomially bounded processing times, we provide a quasipolynomial algorithm which produces a schedule whose value has an additive error proportional to the weighted sum of the due dates. We also investigate the performance of algorithms for minimizing the related total weighted late work objective. (c) 2006 Elsevier B.V. All rights reserved.
暂无评论