bluuebunny/crossref_metadata_2025 huggingface dataset:
Statistical procedures for estimating branch flows and total network flow
Authors: Wells Charles E. , Evans James R.
Published: May 2007

The problem fo estimating branch flows and total network flow in a directed acyclic network is important in diverse applications, such as: (1) in the measurement of rainfall and water run off and (2) in cash control as cash receipts move through an accounting system. In this paper, a variety of network flow estimation problems are examined, where the measurement errors of the observed branch flows may be correlated. Procedures are presented which produce branch flow estimates that conserve flow when observations of flow are available on all network branches and which produce total network flow estimates when observations of flow are available on only a subset of network branches. The latter procedure uses observed flows through proper cut sets. Also included is a discussion of a tractable method of computing biased total network flow estimates. These biased estimates have the potential advantage of having a relatively small variance. All of the estimation procedures presented derive estimates from the solution of appropriately formaulated mathematical programs whose objective function is a quadratic form. An example is included to illustrate the ease of use of the proposed estimation procedures.
Message complexity versus space complexity in fault tolerant broadcast protocols
Authors: Moran Shlomo
Published: May 2007

Let N be a network of asynchronous processors, viewed as vertices, communicating by sending messages over unreliable unidirectional edges, and let r be a specified vertex in N. We consider the problem of constructing efficient and reliable protocols to broadcast messages from r to all other vertices of N: Suppose that for some vertex v in N, at least k edges must be deleted in order to disconnect v from r; we say that a protocol PR, this message will eventually reach v. A protocol is faithful if it is reliable fro all vertices of the network. A general lower bound on the message complexity of faithful protocols, which is at most linear in the network size, is given. It is also shown that this bound can always be achieved by protocols which use the local memories of the vertices to record messages. On the other hand, it is shown that for certain networks, all faithful protocols that use no memory for local computations have a message complexity which is exponential in the network sixe. A characterization of networks that hve faithful protocosl with optimal message and space complexities is also given.
Multiplicative improvements in network reliability bounds
Authors: Brecht Timothy B. , Colbourn Charles J.
Published: May 2007

Multiplictive inequalities for reliability bounds are derived, by observing that certain reliability measures are positively correlated. These inequalities can be used to obtain substantial improvements on available bounds for network reliability.
A branch and bound algorithm for the multiple depot vehicle scheduling problem
Authors: Carpaneto G. , Dell'amico M. , Fischetti M. , Toth P.
Published: May 2007

The Vehicle Scheduling Problem concerns the assigning of a set of time‐tabled trips to vehicles so as to minimize a given cost function. We consider the NP‐hard Multiple Depot case in which, in addition, one has to assign vehicles to depots. Different lower bounds based on assigment relaxation and on connectivity constraints are presented and combined in an effective bounding procedure. A strong dominance procedure derived from new dominance criteria also described. A branch and bound algorithm is finally proposed. Computational results are given.
Balancing large social accounting matrices with nonlinear network programming
Authors: Zenios Stavros A. , Drud Arne , Mulvey John M.
Published: May 2007

We formulate the problem of optimally adjusting the components of a large matrix to satisfy consistency requirements as a nonlinear network optimization model. An efficient network optimization algorithm—GENOS—is incorporated in a user friendly modeling system—GAMS. The resulting software is used for balancing large Social Accounting Matrices (SAM). We assemble a library of SAM models from developing countries and report computational results.
A solvable routing problem
Authors: Gilbert E. N.
Published: May 2007

Stations 1, 2, …,n are interconnected; bij channels join stations i and j. Channels may be grouped together in cables to reruce cost. A Routing problem requires a channel layout (or network of cables) that has minimum cost. The cost of a cable is taken to be independent of its length but a function f(k) of the cable size k. That kind of cost is unusual in practice, but might be appropriate if the “cable” is actually a satellite link. Requiring f(k) to be concave gives a discount for large cables. That imposes a number of special properties on the minimizing network. An extra assumption bij = b, a constant for all i, j, produces a solvable problem. Depending on the shape of f(k), the solution network is either a complete graph or a particular kind of tree.
The continuous p‐median of a network
Authors: Hansen Pierre , Labbé Martine
Published: May 2007

The distance between an edge and a point of a network N is defined as the maximum distance from that point to any point on that edge. A continuous median of N is a point of N such that the sum of the distances between all edges and that point is minimum. A continuous p‐median is a set of p points of N such that the sum for all edges of the distance to the closest poit of that set is minimum. It is shown that the set of vertices and middle points of edges always contaisn a continuous p‐median. Therefore, powerful algorithms for the usual p‐median problem can be brought to bear. Moreover, algorithms requiring O(m2) operations in worst case for determining the set of all continuous and conditional continuous medians of N are obtained. A linear algorithm for the set of all continuous medians of a tree is also provided.
Tracing the characteristic curve of a quadratic black box
Authors: Sun Jie
Published: May 2007

A quadratic black box is a two‐port network with each arc incurring a quadratic cost. This paper studies the properties of the minimum cost function of a quadratic black box with respect to an external flow input. An algorithm is presented with a numerical example for determining the subdifferential mapping of the minimum cost function. The algorithm can be applied to the piecewise quadratic case without change. If all data satisfy the commensurability condition, the algorithm terminates in a finite number of steps.
On the construction of minimal broadcast networks
Authors: Gargano Luisa , Vaccaro Ugo
Published: May 2007

Broadcast is the task of transmitting a message originated at a node in a network to all the other nodes. In this paper, we consider the problem of constructing minimal broadcast networks, that is, communication networks such that broadcast can be performed, from any node, in minimum time. The algorithms we propose allow us to improve known bounds on the minimum number of communication lines needed in minimal broadcast networks. We give some numerical evidence that our algorithms also perform well in practice.
Designing optimal fault‐tolerant star networks
Authors: Farrag Abdel Aziz , Dawson Robert J.
Published: May 2007

The advance in VLSI technology and the continuing decline in the cost of computer hardware have made the construction of complex networks with many processors economically feasible. Due to the complexity of such systems, reliability has become a major issue. In some applications, it is critical that the system must be able to operate correctly despite the presence of certain faults. Multiprocessor networks with such capability are called fault‐tolerant networks. These networks increase reliability by replicating some of the basic components, i.e., by including spare processors and interconnection links. The problem that arises naturally is that of minimizing the spare components that are needed to tolerate failure. In this paper, we consider this problem when the network under consideration is organized in the form of a star. The paper describes how to design optimal m‐FT (m‐fault‐tolerant) graphs with respect to the star configuration, for all values of m ≥ 0.
A location model for a facility operating as an M/G/k queue
Authors: Batta Rajan , Berman Oded
Published: May 2007

This paper considers the problem of locating a single facility on a network that operates as an M/G/k queue, in which the average queueing delay is approximated by using a result in Nozaki and Ross [J. Appl. Prob. 15 (1978) 826–834]. Special consideration is given to the case of a tree network. Localization and sensitivity results are provided, together with appropriate intuitive explanations. We present an illustrative numerical example and provide a brief discussion of our computational experiences with the model. We also use discrete‐event simulation to test the effectiveness of the Nozaki and Ross approximation in the context of finding a good facility location—our results indicate that their approximation is adequate for this purpose.
A set‐partitioning‐based exact algorithm for the vehicle routing problem
Authors: Agarwal Yogesh , Mathur Kamlesh , Salkin Harvey M.
Published: May 2007

In this paper, we discuss a computationally viable algorithm based on a set‐partitioning for‐mulation of the Vehicle Routing Problem (VRP). Implementation strategies based on theoretical as well as empirical results are developed. Some computational results are presented. It is shown that a set‐partitioning formulation to the VRP, although well known for a long time, deserves considerable research efforts beyond those we present here.
A general dynamic spatial price network equilibrium model with gains and losses
Authors: Nagurney Anna , Aronson Jay
Published: May 2007

This paper presents a general dynamic spatial price network equilibrium model with gains and losses, which contains as special cases both dynamic and static models studied earlier. This framework through the use of multipliers has the capability of handling directly agricultural markets for perishable commodities and financial markets. Alternative variational inequality formulations are given and then exploited (akin to the work for dynamic problems without gains and losses) to construct a Gauss–Seidel‐type decomposition scheme. Computational experience for this scheme and for an equilibration multiplier method is given for a variety of large‐scale problems.
On designing a network to defend against random attacks of radius two
Authors: Finbow A. S. , Hartnell B. L.
Published: May 2007

This paper considers the following variation on the construction of a reliable communication network. Whenever a vertex is attacked, all vertices within distance 2 are also destroyed (or fail) indirectly. We are interested in designing a connected graph (undirected, all edges of length one) on p vertices such that when a random subset of the vertices are attacked the expected number of vertices that are destroyed (directly and indirectly) is minimized. It is assumed that any of the 2p subsets of vertices is equally likely to be attacked. The optimal structure is determined for all p and is shown to be one of five patterns depending on r where p = 5t + r.
Probabilistic analysis of an lp relaxation bound for the steiner problem in networks
Authors: Jain Anjani
Published: May 2007

We investigate probabilistically the relative tightness of a linear programming relaxation bound for an integer programming formulation of the Steiner tree problem in networks. Under two different random modesl of the network, we show that the aggregate linear programming relaxation provides a rapidly diverging bound for the optimal Steiner tree and characterize the rates of divergence.
Time bounds on fault‐tolerant broadcasting
Authors: Peleg David , Schäffer Alejandro A.
Published: May 2007

Broadcasting is the process by which a message originated at one vertex is delivered to all other vertices of a network, subject to the restriction that a vertex may participate in only one message transfer during a given time unit. A k fault‐tolerant broadcasting scheme is a calling scheme that gurantees the completion of the broadcast in the presence of up to k link failures. Let Tk(n) denote the minimum time required for k fault‐tolerant broadcasting in an n‐vertex network. Liestman [Networks 15 (1985) 159–171] showed that for every n and k such that n − 2 ≥ k ≥ 1, Tk(n) ⩾ [log n]+k. This paper establishes a matching upper bound, showing that for such n and k, Tk(n) ϵ O (log n +k). In particular, we present various efficient broadcasting schemes achieving almost optimal multiplicative constants. Our best upper bound uses new partial results on a tree‐packing problem that may be of independent interest.
Exact and heuristic algorithms for the weighted feedback arc set problem: A special case of the skew‐symmetric quadratic assignment problem
Authors: Flood Merrill M.
Published: May 2007

This paper presents algorithms for finding exact and approximate solutions for the weighted feedback are set problem, determining a minimum‐cardinality set of ares that breaks all cycles in a directed graph. This is also the problem of finding a group rank ordering given the rank orders for each member of a group. The algorithms have many other applications. Mathematically, the problem is that of finding a permutation matrix P that maximizes the sum of the elements above the principal diagonal of P1 WP where W is a skew‐symmetric matrix of order n. This is a special case of the Koopmans‐Beckmann quadratic assignment problem. Computational experience is reported for a sample of randomly generated problems, including comparisons with results obtained using algorithms three other authors have developed for solving the more general quadratic assignment problem. For our sample, using randomly generated problems, the computational time required for calculating all exact solutions for each problem is approximately T(n) = c2.232n, where c = 9.8764E ‐ 6 and T(20) = 93 s for the Cray X‐MP/48 supercomputer. For our sample, the computational time required for calculating one approximate solution is approximately T(n) = an4,1, where a = 3.0361E ‐ 8 and T(250) = 206 s for the Cray.
A network model for the rotating workforce scheduling problem
Authors: Balakrishnan Nagraj , Wong Richard T.
Published: May 2007

The rotating workforce scheduling problem involves the construction of an efficient sequence of work and rest periods spanning over a number of weeks. This schedule must satisfy the workforce requirements during the different shifts of each day and conform to all the other conditions imposed on the work/rest periods and their sequence. We consider the modeling of the rotating workforce scheduling problem as a network flow problem. All the constraints on the problem are incorporated in the network itself, except for the staff‐covering constraints that are treated as side constraints. The optimal solution to the problem corresponds to a path in the network and is identified using a dual‐based approach. The model deals with the issues of rest‐period identification, work/rest period sequencing, and shift scheduling simultaneously and is designed to handle multiple shift cases with time‐varying demands. The procedure, which is capable of solving large‐scale problems, is applied to three well‐known problems in rotating workforce scheduling. The computational results presented indicate that this procedure provides a useful method for solving large‐scale complex problems in workforce scheduling.
An airline tail routing algorithm for periodic schedules
Authors: Wollmer Richard D.
Published: May 2007

This paper gives a tail routing algorithm that meets a flight schedule with a minimum number of aircraft. The flight segments are identical from period to period and form a partially ordered set. The algorithm takes advantage of the periodic nature of the schedule to reduce the problem size. For a domestic airline whose schedule is identical each week, one may solve two problems, each with a seven and one half day time horizon instead of one larger problem over the entire time horizon which may be several months.
Approximation algorithms for covering a graph by vertex‐disjoint paths of maximum total weight
Authors: Moran Shlomo , Newman Ilan , Wolfstahl Yaron
Published: May 2007

We consider the problem of covering a weighted graph G = (V, E) by a set of vertex‐disjoint paths, such that the total weight of these paths is maximized. This problem is clearly NP‐complete, since it contains the Hamiltonian path problem as a special case. Three approximation algorithms for this problem are presented, exhibiting a complexity‐performance trade‐off. First, we develop an algorithm for covering undirected graphs. The time complexity of this algorithm is O(|E|log|E|), and its performance‐ratio is ½. Second, we present an algorithm for covering undirected graphs, whose performance‐ratio is ⅔. This algorithm uses a maximum weight matching algorithm as a subroutine, which dominates the overall complexity of our algorithm. Finally, we develop an algorithm for covering directed graphs, whose performanceratio is ⅔. This algorithm uses a maximum weight bipartite matching algorithm as a subroutine, which dominates the overall complexity of the algorithm.
Directed network reliability: Domination and computing coefficients of the success‐marginal expansion
Authors: Hagstrom Jane Nichols
Published: May 2007

The reliability for communication in a directed network can be expressed as a summation of terms, each of which involves a success‐marginal probability, that is, the probability of an event of the form {the arcs in set S are working}. Satyanarayana and Prabhakar introduced the concept of domination in order to characterize the coefficients of one such expression. This paper observes that domination can be interpreted as a partial derivative of the reliability multinomial and extends results derived for domination to the general class of expressions involving success‐marginal probabilities.
Anti‐stalling pivot rules for the network simplex algorithm
Authors: Goldfarb Donald , Hao Jianxiu , Kai Sheng‐Roan
Published: May 2007

Stalling in the simplex algorithm is defined as an exponentially long sequence of consecutive degenerate pivots without cycling. Pivot rules for the network simplex algorithm that prevent both cycling and stalling are considered. For several of these, the number of consecutive degenerate pivots is shown to be at most k (k + 1)/2, where k is the number of degenerate basic variables. The relationship between these pivot rules for the network simplex algorithm and strongly polynomial simplex variants for solving the shortest path problem is also discussed.
Interconnecting networks in the plane: The steiner case
Authors: Trietsch Dan
Published: May 2007

It is required to interconnect n existing networks in the plane by new links of minimal total length. We assume that the edges of the networks are straight and that it is possible to make connections along the edges or to the vertices. The use o f Steiner points is also allowed. Though the theoretical number of solutions to the problem is uncountable, we prove that it is enough to consider a finite set of locally optimal solutions with a limit on the number of connections along edges. This makes it possible to solve the problem in finite time by methods similar to those used for the Euclidean Steiner tree problem. The problem can be generalized to include flow‐dependent costs for the various links.
Faster exact algorithms for steiner trees in planar networks
Authors: Bern Marshall
Published: May 2007

We improve the time and space complexities of dynamic programming algorithms that compute optimal Steiner trees spanning nodes in planar networks. Our algorithms have special application to the rectilinear Steiner problem.
The stochastic multicommodity flow problem
Authors: Soroush Hossein , Mirchandani Pitu B.
Published: May 2007

This paper formulates and classifies some multicommodity flow problems (MFP) on “stochastic networks.” Here, the arc attributes are not necessarily deterministic, but, rather, are allowed to be probabilistic. Some special cases of the stochastic multicommodity flow problems (SMFP) are considered where the resultant formulations are solvable by existing algorithms for MFP. Specifically, we consider the following problems:

SMFP‐FLOW INDEPENDENT, where the arc travel attributes are random but not dependent on the flows in the network, and

SMFP‐FLOW DEPENDENT, where the stochasticity of arc travel attributes is either due to random demands or due to arc free‐flow travel attributes being probabilistic.

The scenario where the cost function c(w), of travel attribute w, is linear is fully explored‐for both the above problems. Also, some special cases of the problems are studied when c(w) is exponential or quadratic in w. As an illustrative application, some traffic assignment problems on stochastic networks are formulated and solved as SMFPs.
Efficient algorithms for finding maximum cliques of an overlap graph
Authors: Masuda Sumio , Nakajima Kazuo , Kashiwabara Toshinobu , Fujisawa Toshio
Published: May 2007

Let F = {I1, I2,…,In} be a finite family of closed intervals on the real line. Two intervals Ij and Ik in F are said to overlap each other if they intersect but neither one of them contains the other. A graph G = (V, E) is called an overlap graph for F if there is a one‐to‐one correspondence between V and F such that two vertices in V are adjacent to each other if and only if the corresponding intervals in F overlap each other. In this paper, we present two efficient algorithms for finding maximum cliques of an overlap graph when it is given in the form of a family of n intervals. The first algorithm finds a maximum clique in O (n. log n + Min {m, n‐ ω}) time, where m is the number of edges and ω is the size of a maximum clique, respectively, of the graph. The second algorithm generates all maximum cliques in O (n ‐ log n + m + γ) time, where γ is the total sum of their sizes.
A class of bounded approximation algorithms for graph partitioning
Authors: Feo Thomas A. , Khellaf Mallek
Published: May 2007

This paper considers the problem of partitioning the nodes of a weighted graph into k disjoint subsets of bounded size, such that the sum of the weights of the edges whose end vertices belong to the same subset is maximized. A class of approximation algorithms based on matching is presented. These algorithms are shown to yield practical worst‐case bounds when k is large. Extensive empirical experimentation indicates that the methods produce consistently good solutions to an important VLSI design problem in a fraction of the time required by competing methods.
Location of an obnoxious facility on a network: A voting approach
Authors: Labbé Martine
Published: May 2007

We consider the location problem of an obnoxious facility with respect to a finite number of inhabitants, where the inhabitants have specified locations at vertices of a network N. A voting solution, called anti‐Condorcet point, is defined as a point of N such that no other point is farther from a strict majority of inhabitants. On a general network with an odd number of inhabitants, it is shown that there exists a finite set of points that contains all such solutions. An example shows that this result does not directly extend to an even number of inhabitants on a general network. In the special case of a tree network, one of the extreme vertices of a diameter is an anti‐Condorcet point, and a linear algorithm for finding it is presented. Finally, a bound on the maximum decrease of the total distance to the inhabitants is provided when an anti‐Condorcet point is preferred to a “maxisum” location.
On cost allocation in communication networks
Authors: Granot Daniel , Hojati Mehran
Published: May 2007

We consider two cost allocation problems that arise when the prospective users of a communication network seek a fair method for allocating the cost of constructing the network. We assume the network is of minimum cost and its edge capacities are large enough to satisfy requirements for every pair of users. If the requirements are time‐invariant and have to be satisfied simultaneously, the problem of finding a minimum‐cost network is called the simultaneous network synthesis problem, whereas if the requirements can be satisfied for one pair of users at a time, it is called the nonsimultaneous network synthesis problem. We formulate the cost allocation problems arising from the above problems as cooperative games, referred to as the simultaneous and the nonsimultaneous network synthesis games. We prove that both the (equal cost) nonsimultaneous and the simultaneous network synthesis games are convex and provide nonredundant representations of their cores. For the simultaneous network synthesis game, we present a closed‐form expression for the nucleolus and prove that it coincides with the Shapley value. For the (equal cost) nonsimultaneous network synthesis game, we, provide a closed‐form expression for the nucleolus when the requirement structure is tree‐shaped and develop a quadratic time algorithm for computing the Shapley value in this case.
Computing the probability distribution of project duration in a PERT network
Authors: Hagstrom Jane N.
Published: May 2007

The algorithm presented here makes exact computations of characteristics of the probability distribution of project duration for a stochastic project network. Given discrete independent probability distributions for task durations, the algorithm will compute either moments of the project duration distribution or values of the cumulative distribution function of project duration. The algorithm can be used for sensitivity analysis on probability weights since several task duration distributions having the same range can be handled simultaneously with no great increase in computation time requirements.
The probabilistic minimum spanning tree problem
Authors: Bertsimas Dimitris J.
Published: May 2007

In this paper we consider a natural probabilistic variation of the classical minimum spanning tree problem (MST), which we call the probabilistic minimum spanning tree problem (PMST). In particular, we consider the case where not all the points are deterministically present, but are present with certain probability. We discuss the applications of the PMST and find a closed‐form expression for the expected length of a given spanning tree. Based on these expressions, we prove that the problem is NP‐complete. We further examine some interesting combinatorial properties of the problem, establish the relation of the PMST with the MST and the network design problem, and examine some cases where the problem is solvable in polynomial time. We finally characterize the asymptotic behavior of reoptimization strategies, in which we find the MST or the Steiner tree, respectively, among the points that are present on a particular instance, and the PMST, in the case in which points are randomly distributed in the Euclidean plane and in the case in which the costs of the ares are randomly distributed. In both cases the PMST is within constant factors from both strategies.
Combining monte carlo estimates and bounds for network reliability
Authors: Nel Louis D. , Colbourn Charles J.
Published: May 2007

A simplified model of a communications network is a probabilistic graph in which each edge operates with the same probability. The all‐terminal reliability, or probability that all nodes are connected, can be expressed as a polynomial in the edge operation probability. The coefficients of this polynomial are obtained from an interval partitioning of the cographic matroid, and only the first few coefficients can be computed efficiently. One of the best sets of efficiently computable reliability bounds is the Ball‐Provan bounds. These bounds are obtained using the efficiently computable coefficients and can be improved substantially if additional coefficients are known. In this paper, we develop a Monte Carlo method for estimating additional coefficients by randomly sampling over spanning trees of the network. Confidence intervals for all‐terminal reliability are obtained by using these estimates as additional constraints in the Ball‐Provan bounds. This approach has some advantages over conventional Monte Carlo point estimate methods. In particular, the computational complexity does not depend on the reliability of the network.
A characterization of partial 3‐trees
Authors: Satyanarayana A. , Tung L.
Published: May 2007

A k‐tree is defined recursively as follows: The complete graph Kk on k points is a k‐tree. Given a k‐tree G on n ≤ k points, a k‐tree on n + 1 points is obtained by adding a new point u and edges connecting u to every point of a Kk in G. A graph is a partial k‐tree if it is a subgraph of some k‐tree. In this paper, we establish some interesting properties of partial 3‐trees and show that a graph is a partial 3‐tree if and only if it has no subgraph contractible to K5, K2.2.2 C8(1, 4), or K2 ≤ C5. A graph G is said to be contractible to a graph H if H can be obtained from G by a sequence of edge contractions. hitherto, such a characterization of partial k‐trees was known only for the values of k ≤ 2.
Fair dissections of spiders, worms, and caterpillars
Authors: De Simone Caterina , Lucertini Mario , Pallottino Stefano , Simeone Bruno
Published: May 2007

In the present paper we deal with equipartition problems for special classes of trees, i. e., spiders, stars, worms, and caterpillars. We prove that the equipartition problem is NP‐complete for spiders (and, hence, for general trees); on the other hand, we give efficient polynomial‐time algorithms for stars, worms, and caterpillars.
An application of lagrangean decomposition to the resource‐constrained minimum weighted arborescence problem
Authors: Guignard Monique , Rosenwein Moshe B.
Published: May 2007

The resource‐constrained minimum weighted arborescence problem, a 0‐1 integer programming model with application in hierarchical distribution network design, is introduced. Since the model is NP‐hard, an enumeration method is required to solve it to optimality. Lagrangean decomposition, a special form of Lagrangean relaxation, is applied to the model. Both analytically and empirically, Lagrangean decomposition is shown to improve on bounds obtained by a conventional Lagrangean relaxation. An enumeration algorithm, that embeds a specialized Lagrangean dual ascent scheme to solve a Lagrangean decomposition dual, is designed, and problems with up to 1000 0‐1 variables are solved.
Disjoint (s, t)‐cuts in a network
Authors: Wagner Donald K.
Published: May 2007

Consider a graph having distinguished vertices s and t, and a nonnegative, real‐valued cost associated with each edge. This paper considers variations on the problem of finding k pairwise‐disjoint (s, t)‐cuts of minimum total cost. For k = 1, this problem is a version of the well‐known minimum‐cut problem from network‐flow theory and, thus, is solvable in polynomial time. The main result of this paper is that for arbitrary k, the problem can be formulated as a specially structured transshipment problem and, thus, is solvable in polynomial time.
A heuristic algorithm for a network problem with variable upper bounds
Authors: Shetty Bala
Published: May 2007

We present a heuristic algorithm for the solution of a network problem with variable upper bounds. This algorithm is motivated by the desire to exploit the special structure of the variable upper bound (VUB) constraints and to maintain as much of the characteristics of pure network problems as possible. Our solution technique for the VUB problem consists of solving two sequences of pure network problems. One sequence yields tighter lower bounds on the optimal objective value by considering the Lagrangean relaxation in which the VUB constraints are dualized. The second sequence yields upper bounds on the optimal value for the problem. This sequence is obtained by considering a reformulation of the VUB problem based on parametric changes in the variable upper bound. The algorithm has been tested on problems with as many as 1500 nodes, 6600 arcs, and 3000 VUB constraints. Computational experience with the solution of randomly generated fixed‐charge network problems, capacitated warehouse location problems, and production smoothing problems is also reported.
Relaxation methods for the strictly convex multicommodity flow problem with capacity constraints on individual commodities
Authors: Nagamochi Hiroshi , Fukushima Masao , Lbaraki Toshihide
Published: May 2007

We study the multicommodity flow problem that minimizes a strictly convex cost objective function subject to the capacity constraints on individual commodities as well as the total flows in each arc. By making use of its dual, we formulate the problem as a nonlinear unconstrained optimization problem and propose relaxation methods. Computational results show that the proposed methods can practically solve problem instances, for example, with up to 100 nodes, 1000 arcs, and seven commodities.
Algorithms for special cases of rectilinear steiner trees: I. Points on the boundary of a rectilinear rectangle
Authors: Agarwal Pankaj Kumar , Shing Man‐Tak
Published: May 2007

The general rectilinear Steiner tree problem has been proved to be NP‐complete. In this paper, we consider a special case in which the points lie on the boundary of a rectilinear rectangle and give anO(n)algorithm to construct a minimum rectilinear Steiner tree for such points.
Identifying independence in bayesian networks
Authors: Geiger Dan , Verma Thomas , Pearl Judea
Published: May 2007

An important feature of Bayesian networks is that they facilitate explicit encoding of information about independencies in the domain, information that is indispensable for efficient inferencing. This article characterizes all independence assertions that logically follow from the topology of a network and develops a linear time algorithm that identifies these assertions. The algorithm's correctness is based on the soundness of a graphical criterion, calledd‐separation, and its optimality stems from the completeness ofd‐separation. An enhanced version ofd‐separation, calledD‐separation, is defined, extending the algorithm to networks that encode functional dependencies. Finally, the algorithm is shown to work for a broad class of nonprobabilistic independencies.
An ordered examination of influence diagrams
Authors: Shachter Ross D.
Published: May 2007

Influence diagrams are a directed network representation for decision making under uncertainty. The nodes in the diagram represent uncertain and decision variables, and the arcs indicate probabilistic dependence and observability. This paper examines the graphical orderings underlying the influence diagram and the primitive interchange operations that can reorder the network. These operations are sufficient to determine the maximal independent set and minimal relevant sets for any given inference problem, and a linear time algorithm is developed to obtain those sets. This framework is also used to examine and explain properties of the time structure of general influence diagrams with decisions.
Sequential updating of conditional probabilities on directed graphical structures
Authors: Spiegelhalter David J. , Lauritzen Steffen L.
Published: May 2007

A directed acyclic graph or influence diagram is frequently used as a representation for qualitative knowledge in some domains in which expert system techniques have been applied, and conditional probability tables on appropriate sets of variables form the quantitative part of the accumulated experience. It is shown how one can introduce imprecision into such probabilities as a data base of cases accumulates. By exploiting the graphical structure, the updating can be performed locally, either approximately or exactly, and the setup makes it possible to take advantage of a range of well‐established statistical techniques. As examples we discuss discrete models, models based on Dirichlet distributions and models of the logistic regression type.
Probabilistic similarity networks
Authors: Heckerman David
Published: May 2007

We address the pragmatics of constructing normative expert systems and examine the influence diagram as a potential framework for representing knowledge in such systems. We introduce an extension of the influence‐diagram representation called asimilarity network.A similarity network is a tool for constructing large and complex influence diagrams. The representation allows a user to construct independent influence diagrams for subsets of a given domain. A valid influence diagram for the entire domain can then be constructed from the individual diagrams. Similarity networks represent forms of conditional independence that are not represented conveniently in an ordinary influence diagram. We discuss in detail one such conditional independence, calledsubset independence, and examine how similarity networks exploit this form of independence to facilitate the construction of an influence diagram. Also, we investigate the assessment of probability distributions for influence diagrams. We see that similarity networks exploit subset independence to simplify such probability assessments. We introduce a representation that is closely related to similarity networks, called apartition.This representation further exploits subset independence to simplify probability assessment. Finally, we examine a real‐world normative expert system for the diagnosis of lymph‐node pathology, called Pathfinder. The similarity‐network and partition representations played a crucial role in the construction of this expert system.
An algebra of bayesian belief universes for knowledge‐based systems
Authors: Jensen Finn Verner , Olesen Kristian G. , Andersen Stig Kjaer
Published: May 2007

Causal probabilistic networks (CPNs) have proved to be a useful knowledge representation tool for modeling domains where causal relations‐in a broad sense‐are a natural way of relating domain concepts and where uncertainty is inherited in these relations. The domain is modeled in a CPN by use of a directed graph where the nodes represent concepts in the domain and the arcs represent causal relations. Furthermore, the quantitative relation between a node and its immediate causes is expressed as conditional probabilities. During the last few years, several schemes based on probability theory for incorporating and propagating new information throughout a CPN has emerged. As long as the domain can be modeled by use of a singly connected CPN (i. e., no more than one path between any pair of nodes), the schemes operate directly in the CPN and perform conceptually simple operations in this structure. When it comes to more complicated structures such as multiply connected CPNs (i. e., more than one path is allowed between pairs of nodes), the schemes operate in derived structures where the embedded domain knowledge no longer is as explicit and transparent as in the CPN. Furthermore, the simplicity in the operations is lost also. This report outlines a scheme‐the algebra ofBayesian belief universes‐for absorbing and propagating evidence in multiply connected CPNs. The scheme provides a secondary structure,a junction tree, and a simple set of algebraic operations between objects in this structure,Collect EvidenceandDistribute Evidence.These are the basic tools for making inference in a CPN domain model and yield a calculus as simple as in the case of singly connected CPNs.
A randomized approximation algorithm for probabilistic inference on bayesian belief networks
Authors: Chavez R. Martin , Cooper Gregory F.
Published: May 2007

Researchers in decision analysis and artificial intelligence (AI) have used Bayesian belief networks to build probabilistic expert systems. Using standard methods drawn from the theory of computational complexity, workers in the field have shown that the problem of probabilistic inference in belief networks is difficult and almost certainly intractable. We have developed a randomized approximation scheme, BN‐RAS, for doing probabilistic inference in belief networks. The algorithm can, in many circumstances, perform efficient approximate inference in large and richly interconnected models. Unlike previously described stochastic algorithms for probabilistic inference, the randomized approximation scheme (ras) computes a priori bounds on running time by analyzing the structure and contents of the belief network. In this article, we describe BN‐RAS precisely and analyze its performance mathematically.
Graphical inference in qualitative probabilistic networks
Authors: Wellman Michael P.
Published: May 2007

Qualitative probabilistic networks (QPNs) are abstractions of influence diagrams that encode constraints on the probabilistic relation among variables rather than precise numeric distributions. Qualitative relations express monotonicity constraints on direct probabilistic relations between variables or on interactions among the direct relations. Like their numeric counterpart, QPNs facilitate graphical inference: methods for deriving qualitative relations of interest via graphical transformations of the network model. However, query processing in QPNs exhibits, computational properties quite different from basic influence diagrams. In particular, the potential for information loss due to the incomplete specification of probabilities poses the new challenge of minimizing ambiguity. Analysis of the properties of QPN transformations reveals several characteristics of admissible graphical inference procedures.
On the construction of optimally reliable graphs
Authors: Smith Derek H. , Doty Lynne L.
Published: May 2007

We consider the reliability of regular graphs of degree k in which the vertices of the graph fail independently with probability p. The probability of disconnection is minimized for small values of p if the graph has connectivity k and has the smallest number of vertex cut sets with k vertices. In this paper, we show how to construct such graphs.
Hierarchical solution of network flow problems
Authors: Lyer Anant H. V. , Jarvis John J. , Ratliff H. Donald
Published: May 2007

Given a network flow problem and a partition of its nodes into disjoint sets, we provide an aggregation‐disaggregation procedure that reformulates the problem as the union of network flow subproblems. Each subproblem either involves nodes in a set and their induced arcs or involves nodes and arcs between a pair of node sets. We present a hierarchical solution procedure, based on ficitious play of a two‐person game, that solves each of the subproblems separately at each iteration, retains network structure of each of the subproblems across iterations, generates upper and lower bounds to the objective function value at each iteration, and converges asymptotically to the global optimal solution. We apply the algorithms to a logistics planning model involving uncapacitated transportation problems and provide computational results for problem reformulations based on two different partitions. When the procedure is initialized with a good initial solution, we observe excellent convergence rates for the optimality gap across iterations. We also discuss relationships between our approach and Benders' decomposition and provide an example comparing the objective function values of solutions generated by the two approaches.
Time‐dependent traveling salesman problem–the deliveryman case
Authors: Lucena Abilio
Published: May 2007

We consider a scheme to derive lower bounds for the time‐dependent traveling salesman problem. It involves splitting lower bounds into a number of components and optimizing each of these components. The lower bounds thus derived are shown to be at least as sharp as the ones previously suggested for the problem. We describe a branch‐and‐bound algorithm based on our lower bounding scheme and computationally test it for an instance of the problem known as the traveling deliveryman problem.
Optimal locations and districts of two traveling salesmen on a tree
Authors: Simchi‐Levi David , Berman Oded
Published: May 2007

This paper focuses on the problem of locating on a tree two service units that must service each working day all the customers that require service. The paper includes an O(n2) algorithm to find the optimal locations that minimize the expected distance traveled by the two service units. This algorithm also gives the optimal service territories of the two service units. The algorithm is based on an available O(n) algorithm to find the optimal location of a single service unit on a tree and on a new method to calculate the objective function value of a given location for the single server.
Predicting deadlock in store‐and‐forward networks
Authors: Arbib Claudio , Italiano Gluseppe F. , Panconesl Alessandro
Published: May 2007

We consider the problem of predicting whether a deadlock will necessarily occur in a store‐and‐forward network. We define two versions of this problem, depending on whether or not the routes to be followed by packets are fixed. For networks with only one buffer per vertex, both versions of this problem are shown to be NP‐complete even for simple classes of graphs (among others bipartite graphs, two terminal series‐parallel [TTSP] graphs and therefore planar graphs). On the other hand, the same problems are shown to be polynomially solvable for treelike networks. In this case, two efficient algorithms for checking whether a treelike network with n vertices and p packets is bound to deadlock are proposed. The former has an O(pn) time and space complexity, whereas the latter runs in O(n log n)1 time and requires O(n) space. In the case of multibuffered networks, both versions of the problem are shown to be NP‐complete even on treelike networks.
Efficient algorithms for computing the reliability of permutation and interval graphs
Authors: Aboeifotoh Hosam M. , Colbourn Charles J.
Published: May 2007

A stochastic network in which nodes fail randomly with known probabilities is modeled by a probabilistic graph with unreliable nodes and perfect edges. The K‐terminal reliability of such a network is the probability that there exists a Steiner tree connecting a subset of the nodes K (target nodes). Although the K‐terminal reliability problem has been widely studied for networks with unreliable links, very little is known about the problem for networks with unreliable nodes. We show that computing this measure is computationally difficult, in particular #P‐complete. We then present efficient algorithms for the K‐terminal reliability problem on two classes of perfect graphs; interval graphs and permutation graphs. Computing the reliability on these two classes of graphs is of particular interest since the problem remains #P‐complete for larger classes in the hierarchy of perfect graphs, namely, comparability and chordal graphs. The model presented in this paper is appropriate for radio broadcast networks and for fault‐tolerant multiprocessor networks.
Minimal diameter double‐loop networks: Dense optimal families
Authors: Bermond J.‐C. , Tzvieli Dvora
Published: May 2007

This article deals with the problem of minimizing the transmission delay in Illiac‐type interconnection networks for parallel or distributed architectures or in local area networks. A double‐loop network (also known as circulant) G(n,h), consists of a loop of n vertices where each vertex i is also joined by chords to the vertices i ± h mod n. An integer n, a hop h, and a network G(n,h) are called optimal if the diameter of G(n,h) is equal to the lower bound k when n ∈ R[k] = {2k2 − 2k + 2, …,2k2 + 2k + 1}. We determine new dense families of values of n that are optimal and such that the computation of the optimal hop is easy. These families cover almost all the elements of R[k] if k or k + 1 is prime and cover 92% of all values of n up to 106.