			Home About us Contact

Approximation Algorithms (approximation + algorithms)

Distribution by Scientific Domains

Mathematics and Statistics	81%
Business, Economics, Finance and Accounting	13%

Selected Abstracts

A new distributed approximation algorithm for constructing minimum connected dominating set in wireless ad hoc networks

INTERNATIONAL JOURNAL OF COMMUNICATION SYSTEMS, Issue 8 2005
Bo Gao
Abstract In recent years, constructing a virtual backbone by nodes in a connected dominating set (CDS) has been proposed to improve the performance of ad hoc wireless networks. In general, a dominating set satisfies that every vertex in the graph is either in the set or adjacent to a vertex in the set. A CDS is a dominating set that also induces a connected sub-graph. However, finding the minimum connected dominating set (MCDS) is a well-known NP-hard problem in graph theory. Approximation algorithms for MCDS have been proposed in the literature. Most of these algorithms suffer from a poor approximation ratio, and from high time complexity and message complexity. In this paper, we present a new distributed approximation algorithm that constructs a MCDS for wireless ad hoc networks based on a maximal independent set (MIS). Our algorithm, which is fully localized, has a constant approximation ratio, and O(n) time and O(n) message complexity. In this algorithm, each node only requires the knowledge of its one-hop neighbours and there is only one shortest path connecting two dominators that are at most three hops away. We not only give theoretical performance analysis for our algorithm, but also conduct extensive simulation to compare our algorithm with other algorithms in the literature. Simulation results and theoretical analysis show that our algorithm has better efficiency and performance than others. Copyright © 2005 John Wiley & Sons, Ltd. [source]

Approximation algorithms for combinatorial multicriteria optimization problems

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 1 2000
M. Ehrgott
Abstract The computational complexity of combinatorial multiple objective programming problems is investigated. NP-completeness and #P -completeness results are presented. Using two definitions of approximability, general results are presented, which outline limits for approximation algorithms. The performance of the well-known tree and Christofides' heuristics for the traveling salesman problem is investigated in the multicriteria case with respect to the two definitions of approximability. [source]

Approximation algorithms for general one-warehouse multi-retailer systems

NAVAL RESEARCH LOGISTICS: AN INTERNATIONAL JOURNAL, Issue 7 2009
Zuo-Jun Max Shen
Abstract Logistical planning problems are complicated in practice because planners have to deal with the challenges of demand planning and supply replenishment, while taking into account the issues of (i) inventory perishability and storage charges, (ii) management of backlog and/or lost sales, and (iii) cost saving opportunities due to economies of scale in order replenishment and transportation. It is therefore not surprising that many logistical planning problems are computationally difficult, and finding a good solution to these problems necessitates the development of many ad hoc algorithmic procedures to address various features of the planning problems. In this article, we identify simple conditions and structural properties associated with these logistical planning problems in which the warehouse is managed as a cross-docking facility. Despite the nonlinear cost structures in the problems, we show that a solution that is within ,-optimality can be obtained by solving a related piece-wise linear concave cost multi-commodity network flow problem. An immediate consequence of this result is that certain classes of logistical planning problems can be approximated by a factor of (1 + ,) in polynomial time. This significantly improves upon the results found in literature for these classes of problems. We also show that the piece-wise linear concave cost network flow problem can be approximated to within a logarithmic factor via a large scale linear programming relaxation. We use polymatroidal constraints to capture the piece-wise concavity feature of the cost functions. This gives rise to a unified and generic LP-based approach for a large class of complicated logistical planning problems. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009 [source]

A generalization of the weighted set covering problem

NAVAL RESEARCH LOGISTICS: AN INTERNATIONAL JOURNAL, Issue 2 2005
Jian Yang
Abstract We study a generalization of the weighted set covering problem where every element needs to be covered multiple times. When no set contains more than two elements, we can solve the problem in polynomial time by solving a corresponding weighted perfect b -matching problem. In general, we may use a polynomial-time greedy heuristic similar to the one for the classical weighted set covering problem studied by D.S. Johnson [Approximation algorithms for combinatorial problems, J Comput Syst Sci 9 (1974), 256,278], L. Lovasz [On the ratio of optimal integral and fractional covers, Discrete Math 13 (1975), 383,390], and V. Chvatal [A greedy heuristic for the set-covering problem, Math Oper Res 4(3) (1979), 233,235] to get an approximate solution for the problem. We find a worst-case bound for the heuristic similar to that for the classical problem. In addition, we introduce a general type of probability distribution for the population of the problem instances and prove that the greedy heuristic is asymptotically optimal for instances drawn from such a distribution. We also conduct computational studies to compare solutions resulting from running the heuristic and from running the commercial integer programming solver CPLEX on problem instances drawn from a more specific type of distribution. The results clearly exemplify benefits of using the greedy heuristic when problem instances are large. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2005 [source]

Approximation algorithms for channel allocation problems in broadcast networks

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2006
Rajiv Gandhi
Abstract We study two packing problems that arise in the area of dissemination-based information systems; a second theme is the study of distributed approximation algorithms. The problems considered have the property that the space occupied by a collection of objects together could be significantly less than the sum of the sizes of the individual objects. In the Channel Allocation Problem, there are requests that are subsets of topics. There are a fixed number of channels that can carry an arbitrary number of topics. All the topics of each request must be broadcast on some channel. The load on any channel is the number of topics that are broadcast on that channel; the objective is to minimize the maximum load on any channel. We present approximation algorithms for this problem, and also show that the problem is MAX-SNP hard. The second problem is the Edge Partitioning Problem addressed by Goldschmidt, Hochbaum, Levin, and Olinick (Networks, 41:13,23, 2003). Each channel here can deliver topics for at most k requests, and we aim to minimize the total load on all channels. We present an O(n1/3),approximation algorithm, and also show that the algorithm can be made fully distributed with the same approximation guarantee; we also generalize the (nondistributed) Edge Partitioning Problem of graphs to the case of hypergraphs. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 47(4), 225,236 2006 [source]

Approximation algorithms for the k-source multicast tree construction problem

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2006
Paraskevi Fragopoulou
Abstract Given an undirected graph with nonnegative weights on its edges, a group of source nodes, and a group of destination nodes, we investigate the problem of constructing a multicast tree that minimizes the sum of distances from a destination node to all sources. This problem has been proven to be NP-complete. In this article, we show that there is a point c of the graph such that a shortest paths tree constructed from c is a 2-approximation to the problem, a significant improvement over the previous results, and we present an efficient approximation algorithm. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 47(3), 178,183 2006 [source]

Approximation algorithms for finding low-degree subgraphs

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2004
Philip N. Klein
Abstract We give quasipolynomial-time approximation algorithms for designing networks with a minimum degree. Using our methods, one can design networks whose connectivity is specified by "proper" functions, a class of 0,1 functions indicating the number of edges crossing each cut. We also provide quasipolynomial-time approximation algorithms for finding two-edge-connected spanning subgraphs of approximately minimum degree of a given two-edge-connected graph, and a spanning tree (branching) of approximately minimum degree of a directed graph. The degree of the output network in all cases is guaranteed to be at most (1 + ,) times the optimal degree, plus an additive O(log1+,n) for any , > 0. Our analysis indicates that the degree of an optimal subgraph for each of the problems above is well estimated by certain polynomially solvable linear programs. This suggests that the linear programs we describe could be useful in obtaining optimal solutions via branch and bound. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(3), 203,215 2004 [source]

Approximation algorithms for constructing wavelength routing networks

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 1 2002
Refael Hassin
Abstract Consider a requirement graph whose vertices represent customers and an edge represents the need to route a unit of flow between its end vertices along a single path. All these flows are to be routed simultaneously. A solution network consists of a (multi)graph on the same set of vertices, such that it is possible to route simultaneously all of the required flows in such a way that no edge is used more than K times. The SYNTHESIS OF WAVELENGTH ROUTING NETWORK (SWRN) problem is to compute a solution network of a minimum number of edges. This problem has significant importance in the world of fiber-optic networks where a link can carry a limited amount of different wavelengths and one is interested in finding a minimum-cost network such that all the requirements can be carried in the network without changing the wavelength of a path at any of its internal vertices. In this paper, we prove that the SWRN problem is NP-hard for any constant K (K , 2). Then, we assume that GR is a clique with n vertices and we find an "almost" optimal solution network for all values of K (K = o(n)) and present a Min{(K + 1)/2, 2 + 2/(K , 1)}-approximation algorithm for the general case and a 2-approximation algorithm for d -regular graphs. © 2002 Wiley Periodicals, Inc. [source]

Approximation algorithms for combinatorial multicriteria optimization problems

OPTIMAL MULTIPLE STOPPING AND VALUATION OF SWING OPTIONS

MATHEMATICAL FINANCE, Issue 2 2008
René Carmona
The connection between optimal stopping of random systems and the theory of the Snell envelop is well understood, and its application to the pricing of American contingent claims is well known. Motivated by the pricing of swing contracts (whose recall components can be viewed as contingent claims with multiple exercises of American type) we investigate the mathematical generalization of these results to the case of possible multiple stopping. We prove existence of the multiple exercise policies in a fairly general set-up. We then concentrate on the Black,Scholes model for which we give a constructive solution in the perpetual case, and an approximation procedure in the finite horizon case. The last two sections of the paper are devoted to numerical results. We illustrate the theoretical results of the perpetual case, and in the finite horizon case, we introduce numerical approximation algorithms based on ideas of the Malliavin calculus. [source]

Approximability of unsplittable shortest path routing problems,

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 1 2009
Andreas Bley
Abstract In this article, we discuss the relation of unsplittable shortest path routing (USPR) to other routing schemes and study the approximability of three USPR network planning problems. Given a digraph D = (V,A) and a set K of directed commodities, an USPR is a set of flow paths P, (s,t) , K, such that there exists a metric , = (,a) , Z with respect to which each P is the unique shortest (s,t)-path. In the Min-Con-USPR problem, we seek an USPR that minimizes the maximum congestion over all arcs. We show that this problem is NP-hard to approximate within a factor of O(|V|1,,), but polynomially approximable within min(|A|,|K|) in general and within O(1) if the underlying graph is an undirected cycle or a bidirected ring. We also construct examples where the minimum congestion that can be obtained by USPR is a factor of ,(|V|2) larger than that achievable by unsplittable flow routing or by shortest multipath routing, and a factor of ,(|V|) larger than that achievable by unsplittable source-invariant routing. In the CAP -USPR problem, we seek a minimum cost installation of integer arc capacities that admit an USPR of the given commodities. We prove that this problem is NP-hard to approximate within 2 , , even in the undirected case, and we devise approximation algorithms for various special cases. The fixed charge network design problem FC-USPR, where the task is to find a minimum cost subgraph of D whose fixed arc capacities admit an USPR of the commodities, is shown to be NPO-complete. All three problems are of great practical interest in the planning of telecommunication networks that are based on shortest path routing protocols. Our results indicate that they are harder than the corresponding unsplittable flow or shortest multi-path routing problems. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009 [source]

Minimizing SONET Add-Drop Multiplexers in optical UPSR networks using the minimum number of wavelengths

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2009
Yong Wang
Abstract In SONET/WDM optical networks, a high-speed wavelength channel is usually shared by multiplexed low-rate network traffic demands. The multiplexing is known as traffic grooming and carried out by SONET Add-Drop Multiplexers (SADM). The maximum number of low-rate traffic demands that can be multiplexed into one wavelength is called the grooming factor. Because SADMs are expensive network devices, a key optimization problem in optical network design is to groom a given set of low-rate traffic demands such that the number of required SADMs is minimized. This optimization problem is challenging and NP-hard even for Unidirectional Path-Switched Ring networks with unitary duplex traffic demands. In this article, we propose two linear-time approximation algorithms for this NP-hard problem based on a novel graph partitioning approach. Both algorithms achieve better worst case performance than the previous algorithms. We also show that the upper bounds obtained by our algorithms are very close to the lower bounds for some instances. In addition, both of our algorithms use the minimum number of wavelengths, which are precious resources as well in optical networks. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009 [source]

Approximate L(,1,,2,,,,t)-coloring of trees and interval graphs

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2007
Alan A. Bertossi
Abstract Given a vector (,1,,2,,,,t) of nonincreasing positive integers, and an undirected graph G = (V,E), an L(,1,,2,,,,t)-coloring of G is a function f from the vertex set V to a set of nonnegative integers such that ,f(u) , f(v), , ,i, if d(u,v) = i, 1 , i , t, where d(u,v) is the distance (i.e., the minimum number of edges) between the vertices u and v. An optimal L(,1,,2,,,,t)-coloring for G is one minimizing the largest integer used over all such colorings. Such a coloring problem has relevant applications in channel assignment for interference avoidance in wireless networks. This article presents efficient approximation algorithms for L(,1,,2,,,,t)-coloring of two relevant classes of graphs,trees, and interval graphs. Specifically, based on the notion of strongly simplicial vertices, O(n(t + ,1)) and O(nt2,1) time algorithms are proposed to find ,-approximate colorings on interval graphs and trees, respectively, where n is the number of vertices and , is a constant depending on t and ,1,,,,t. Moreover, an O(n) time algorithm is given for the L(,1,,2)-coloring of unit interval graphs, which provides a 3-approximation. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 49(3), 204,216 2007 [source]

Approximation algorithms for channel allocation problems in broadcast networks

Approximation algorithms for finding low-degree subgraphs

The 2-path network problem

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2004
Geir Dahl
Abstract Given a graph with nonnegative edge weights and a set D of node pairs, the 2- path network problem requires a minimum weight set of edges such that the induced subgraph contains a path with one or two edges connecting each pair in D. The problem is NP -hard. We present two integer programming models for the problem and study properties of associated polytopes, including cutting planes. Two approximation algorithms are suggested and analyzed. Some computational experience is reported. © 2004 Wiley Periodicals, Inc. [source]

Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms,

RANDOM STRUCTURES AND ALGORITHMS, Issue 3 2008
Petros Drineas
Abstract Recent work in the analysis of randomized approximation algorithms for NP -hard optimization problems has involved approximating the solution to a problem by the solution of a related subproblem of constant size, where the subproblem is constructed by sampling elements of the original problem uniformly at random. In light of interest in problems with a heterogeneous structure, for which uniform sampling might be expected to yield suboptimal results, we investigate the use of nonuniform sampling probabilities. We develop and analyze an algorithm which uses a novel sampling method to obtain improved bounds for approximating the Max-Cut of a graph. In particular, we show that by judicious choice of sampling probabilities one can obtain error bounds that are superior to the ones obtained by uniform sampling, both for unweighted and weighted versions of Max-Cut. Of at least as much interest as the results we derive are the techniques we use. The first technique is a method to compute a compressed approximate decomposition of a matrix as the product of three smaller matrices, each of which has several appealing properties. The second technique is a method to approximate the feasibility or infeasibility of a large linear program by checking the feasibility or infeasibility of a nonuniformly randomly chosen subprogram of the original linear program. We expect that these and related techniques will prove fruitful for the future development of randomized approximation algorithms for problems whose input instances contain heterogeneities. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008 [source]

A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems,

RANDOM STRUCTURES AND ALGORITHMS, Issue 3 2002
Eran Halperin
We obtain improved semidefinite programming based approximation algorithms for all the natural maximum bisection problems of graphs. Among the problems considered are: MAX -BISECTION,partition the vertices of the graph into two sets of equal size such that the total weight of edges connecting vertices from different sides is maximized; MAX -VERTEX-COVER,find a set containing half of the vertices such that the total weight of edges touching this set is maximized; MAX -DENSE-SUBGRAPH,find a set containing half of the vertices such that the total weight of edges connecting two vertices from this set is maximized; and MAXUNCUT,partition the vertices into two sets of equal size such that the total weight of edges that do not cross the cut is maximized. We also consider the directed versions of these problems, such as MAX -DIRECTED-BISECTION and MAX -DIRECTED-UNCUT. These results can be used to obtain improved approximation algorithms for the unbalanced versions of the partition problems mentioned above, where we want to partition the graph into two sets of size and , where is not necessarily . Our results improve, extend and unify results of Frieze and Jerrum, Feige and Langberg, Ye, and others. All these results may be viewed as extensions of the MAX CUT algorithm of Goemans and Williamson, and the MAX 2-SAT and MAX DI-CUT algorithms of Feige and Goemans. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 20:382,402, 2002 [source]