bluuebunny/crossref_metadata_2025_split huggingface dataset:
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

AbstractThe 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

AbstractWe 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

AbstractStations 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

AbstractThe 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

AbstractA 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

AbstractBroadcast 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

AbstractThe 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

AbstractThis 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

AbstractIn 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

AbstractThis 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

AbstractThis 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

AbstractWe 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

AbstractBroadcasting 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

AbstractThis 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

AbstractThe 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

AbstractThis 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

AbstractWe 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

AbstractThe 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

AbstractStalling 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

AbstractIt 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.
The stochastic multicommodity flow problem
Authors: Soroush Hossein , Mirchandani Pitu B. 
Published: May 2007

AbstractThis 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

AbstractLet 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

AbstractThis 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

AbstractWe 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

AbstractWe 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

AbstractThe 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.