Abstract We consider the min‐cost flow problem on multiple networks defined on duplicates of the same directed graph. The problem is to compute feasible flows such that the sum of flow costs is minimized subject to network demands and coupling constraints that force identical flows on duplicate copies of the same edge for a subset of “special” edges. We focus on whether such a problem has an integer optimal solution. For the case of integer capacities and demands and flow equality on a single edge, there is always an integer optimal solution and it can be found efficiently. For flow equality on multiple edges, we characterize the cases, with respect to the number of special edges and the number of networks, where if the graph is series‐parallel then an integer optimal solution exists for all possible capacity and cost functions.

We consider the well-known minimum quadratic assignment problem. In this problem we are given two n × n nonnegative symmetric matrices A = ( a ij ) and B = ( b ij ). The objective is to compute a permutation π of V = {1,…, n } so that ∑ i , j ∈ V i ≠ j a π( i ),π( j ) b i , j is minimized. We assume that A is a 0/1 incidence matrix of a graph, and that B satisfies the triangle inequality. We analyze the approximability of this class of problems by providing polynomial bounded approximations for some special cases, and inapproximability results for other cases.

Let G = ( V , E ) be an undirected graph, with three numbers d 0 ( e ) ≥ d 1 ( e ) ≥ d 2 ( e ) ≥ 0 for each edge e ∈ E . A solution is a subset U ⊆ V and d i ( e ) represents the cost contributed to the solution by the edge e if exactly i of its endpoints are in the solution. The cost of including a vertex v in the solution is c ( v ). A solution has cost that is equal to the sum of the vertex costs and the edge costs. The minimum generalized vertex cover problem is to compute a minimum cost set of vertices. We study the complexity of the problem with the costs d 0 ( e ) = 1, d 1 ( e ) = α and d 2 ( e ) = 0 ∀ e ∈ E and c ( v ) = β∀ v ∈ V , for all possible values of α and β. We also provide 2-approximation algorithms for the general case.

Consider a graph problem which is associated with a parameter, for example, that of finding a longest tour spanning k vertices. The following question is natural: Is there a small subgraph that contains an optimal or near optimal solution for every possible value of the given parameter? Such a subgraph is said to be robust . In this article we consider the problems of finding heavy paths and heavy trees of k edges. In these two cases, we prove surprising bounds on the size of a robust subgraph for a variety of approximation ratios. For both problems, we show that in every complete weighted graph on n vertices there exists a subgraph with approximately α/1−α 2 n edges that contains an α-approximate solution for every k = 1,…, n − 1. In the analysis of the tree problem, we also describe a new result regarding balanced decomposition of trees. In addition, we consider variants in which the subgraph itself is restricted to be a path or a tree. For these problems, we describe polynomial time algorithms and corresponding proofs of negative results.

In the weighted set-cover problem we are given a set of elements $E=\{ e_1,e_2, \ldots ,e_n \}$ and a collection $\cal F$ of subsets of E, where each $S \in \cal F$ has a positive cost $c_{S}$. The problem is to compute a subcollection $SOL$ such that $\bigcup_{S\in SOL}S_j=E$ and its cost $\sum_{S\in SOL}c_S$ is minimized. When $|S|\le k\ \forall S\in\cal F$ we obtain the weighted k-set cover problem. It is well known that the greedy algorithm is an $H_k$-approximation algorithm for the weighted k set cover, where $H_k=\sum_{i=1}^k {1 \over i}$ is the kth harmonic number, and that this bound is exact for the greedy algorithm for all constant values of k. In this paper we give the first improvement on this approximation ratio for all constant values of k. This result shows that the greedy algorithm is not the best possible for approximating the weighted set cover problem. Our method is a modification of the greedy algorithm that allows the algorithm to regret.

Given an undirected graph G=(V,E) with |V|=n and |E|=m, nonnegative integers c e and d e for each edge $e \in E$, and a bound D, the constrained minimum spanning tree problem (CST) is to find a spanning tree T=(V,E T ) such that $\sum_{e \in E_T} d_e \leq D$ and $\sum_{e \in E_T} c_e$ is minimized. We present an efficient polynomial time approximation scheme (EPTAS) for this problem. Specifically, for every $\epsilon>0$ we present a $(1+\epsilon)$-approximation algorithm with time complexity $O((\frac{1}{\epsilon})^{O(\frac{1}{\epsilon})}n^4)$. Our method is based on Lagrangian relaxation and matroid intersection.

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.

We consider complete graphs with nonnegative edge weights. A p-matching is a set of p disjoint edges. We prove the existence of a maximal (with respect to inclusion) matching M that contains for any $p\le|M|$ p edges whose total weight is at least ${1\over \sqrt 2}$ of the maximum weight of a p-matching. We use this property to approximate the metric maximum clustering problem with given cluster sizes.

Given a directed graph G and an arc weight function $w: E(G)\rightarrow\mathbb{R}_+$, the maximum directed cut problem ({\sc max dicut}) is that of finding a directed cut $\delta (X)$ with maximum total weight. In this paper we consider a version of {\sc max dicut}---{\sc max dicut} with given sizes of parts or {\sc max dicut with gsp}---whose instance is that of {\sc max dicut} plus a positive integer p, and it is required to find a directed cut $\delta (X)$ having maximum weight over all cuts $\delta (X)$ with $|X|=p$. Our main result is a $0.5$-approximation algorithm for solving the problem. The algorithm is based on a tricky application of the pipage rounding technique developed in some earlier papers by two of the authors and a remarkable structural property of basic solutions to a linear relaxation. The property is that each component of any basic solution is an element of a set $\{0,\delta,1/2,1-\delta,1 \}$, where $\delta$ is a constant that satisfies $0 < \delta < 1/2$ and is the same for all components.

A set V and a collection of (possibly nondisjoint) subsets are given. Also given is a real matrix describing distances between elements of V. A cover is a subset of V containing at least one representative from each subset. The multiple-choice minimum-diameter problem is to select a cover of minimum diameter. The diameter is defined as the maximum distance between any pair of elements in the cover. The multiple-choice dispersion problem, which is closely related, asks us to maximize the minimum distance between any pair of elements in the cover. The problems are NP-hard. We present polynomial time algorithms for approximating special cases and generalizations of these basic problems, and we prove in other cases that no such algorithms exist (assuming P ≠ NP). © 2000 John Wiley & Sons, Inc.

We consider a delivery problem on a network in which nodes have supplies or demands for certain products and arcs have lengths satisfying the triangle inequality. A vehicle of infinite capacity travels through the network, carrying products to their destinations, and is limited in that it can carry only a single type of product at a time. The general problem asks for a shortest delivery route of all products from their origin to their destination. Here, we consider certain restrictions on the delivery paths allowed and compare the quality of the solution of the unrestricted problem to that of the restricted one. Both the general and restricted problems are NP-hard, and we discuss approximation algorithms. We also give a constant factor approximation algorithm for the Clustered Traveling Salesman Problem. © 1997 John Wiley & Sons, Inc.

Abstract Each vertex of a graph initially may contain an object of a known type. A final state, specifying the type of object desired at each vertex, is also given. A single vehicle of unit capacity is available for shipping objects among the vertices. The swapping problem is to compute a shortest route such that a vehicle can accomplish the rearrangement of the objects while following this route. We exhibit several structural properties of shortest routes and develop polynomial approximation algorithms that are variations of a well‐known “patching” algorithm for the traveling salesman problem. We prove tight constant performance guarantees for these algorithms and note as a side product that these bounds hold and are tight also for the latter problem.

Let $P ( 0 ) \in R^{n \times n} $ be a stochastic matrix representing transition probabilities in a Markov Chain. Also, for a matrix $A \in R^{n \times n} $ whose row-sums are zero, let $P( \varepsilon ) \equiv P ( 0 ) + \varepsilon A$ be stochastic and irreducible for all $0 < \varepsilon \leq \varepsilon _{\max } $, for some $\varepsilon_{\max } $. Finally, let $M( \varepsilon )$ be a matrix whose $( i, j )$ entry is the mean passage time from state i to state j when transitions are governed by $P( \varepsilon )$. When the Markov chain associated with $P( 0 )$ is decomposable into a number of independent chains plus a set of transient states, some of the entries of $M( \varepsilon )$ have singularities at zero. The orders of these poles define timescales associated with the process when $\varepsilon $ is small. An algorithm is developed for computing these orders. The only input required is the supports of $P( 0 )$ and A, making the problem a combinatorial one. Finally, it is shown how the orders of the poles of $M( \varepsilon )$ at zero play a role in developing series expansions for $\pi ( \varepsilon )$, the stationary distribution of $P( \varepsilon )$.

The problem of ranking the K-best binary trees with respect to their weighted average leaves’ levels is considered. Both the alphabetic case, where the order of the weights in the sequence $w_1 , \cdots ,w_n $ must be preserved in the leaves of the tree, and the nonalphabetic case, where no such restriction is imposed, are studied. For the alphabetic case a simple algorithm is provided for ranking the K-best trees based on a recursive formula of complexity $O(Kn^3 )$. For nonalphabetic trees two different ranking problems are considered, and for each of them it is shown that the next best tree can be solved by a dynamic programming formula of low complexity order.

A new algorithm is given to find a maximum flow in an undirected planar flow network in $O(n\log ^2 n)$ time, which is faster than the best method previously known by a factor of $\sqrt n /\log n$. The algorithm constructs a transformation of the dual of the given flow network in which differences between shortest distances are equal, under suitable edge correspondences, to edge flows in the given network. The transformation depends on the value of a maximum flow. The algorithm then solves the shortest distances problem efficiently by exploiting certain structural properties of the transformed dual, as well as using a set of cuts constructible in $O(n\log ^2 n)$ time by a known method which is also used to find the requisite flow value. The main result can be further improved by a factor of $\log n/\log^* n$ if a recently developed shortest path algorithm for planar networks is used in place of Dijkstra’s algorithm in each step where shortest paths are computed.

Abstract Okamura and Seymour recently proved two properties of multicommodity flows in undirected planar networks where all the sources and the sinks are on a common face of the underlying graph. One is that a feasible solution is guaranteed whenever each cut's capacity is at least as large as the cut's demand. The second is that if all demands and capacities are integers then the flow values may be chosen half‐integer‐valued. In this paper we use the first property to construct two computational procedures; one examines the existence of a feasible flow, and the other constructs such a flow if one exists. We also show that the construction procedure can be used as an alternative proof to the above properties. Finally we show, by presenting counterexamples, that the half‐integrality property does not necessarily hold when either the graph cannot be drawn in the plane with all sources and sinks on a common face, or the graph is directed.

Abstract The minimum cost network flow problem with set‐constraints is a generalization of the well‐known minimum cost network flow problem, in which bounds on the sum of flows through sets of arcs exist. This paper investigates some variations of this problem, including the polymatroid intersection problem, where for each node two polymatroids are given; one polymatroid constrains flows entering the node, and the other constrains flows leaving it.

Abstract Hoffman's Existence Theorem for circulations gives a necessary and sufficient condition for the existence of a feasible circulation in a directed network with upper and lower bounds on the flow along each of the arcs. This paper presents new existence theorems for more general types of flows in directed networks: flows with gains, two‐commodity flows, and flows with set constraints.