bluuebunny/crossref_metadata_2025_split huggingface dataset:
A multiphase approach to the period routing problem
Authors: Russell Robert A. , Gribbin Dave 
Published: May 2007

AbstractIn this article, we present a multiphase approach to the period routing problem. The period routing problem involves the design of effective vehicle routes that satisfy customer service frequencies over a specified planning horizon. The first phase of analysis consists of a generalized network approximation to achieve an efficient initial solution. The second phase involves an interchange heuristic that reduces distribution costs by solving a surrogate traveling salesman problem. The third phase consists of an interchange heuristic that further reduces the distribution costs by addressing the actual vehicle routes of the period routing problem. A fourth phase utilizes a 0–1 integer model to attempt further improvements. Computational results on test problems indicate that the multiphase approach yields improvements over previous best solutions.
Characterizing stochastic flow networks using the monte carlo method
Authors: Alexopoulos Christos , Fishman George S. 
Published: May 2007

AbstractConsider a flow network G = (𝒱,ℰ) with node set 𝒱 and arc set ℰ = {1, …, e}. Assume that the nodes do not restrict flow transmission and the arcs have random, discrete and independent capacities B1, …, Be, and let B = {B1, …, Be}. Also, let s and t be a pair of nodes in 𝒱, let Λ(B) denote the value of a maximum s–t flow, and let Γ denote a set of s–t cuts. This work describes a highly efficient Monte Carlo sampling plan for estimating the probability that l < Λ(B) ⩽ u, the probability that a cut in Γ is critical and l < Λ(B) ⩽ u, and the probability that a cut in Γ is critical, given that l < Λ(B) ⩽ u. The proposed method takes advantage of an easily computed upper bound on the probability that l < Λ(B) ⩽ u, which is a function of both l and u to gain its computational advantage. The article also describes techniques for computing confidence intervals that are valid for any sample size. Algorithms for implementing the proposed sampling experiment are included, and an example illustrates the efficiency of the proposed method.
The steiner problem in the hypercube
Authors: Miller Zevi , Perkel Manley 
Published: May 2007

AbstractLet Q(n) be the n‐dimensional hypercube, and X, a set of points in Q(n). The Steiner problem for the hypercube is to find the smallest possible number L(n,X) of edges in any subtree of Q(n) that spans X. We obtain the following results:

An exact formula for L(n,X), when |X| ≤ 5.
The bound L(n,X) ≤ (nk+1) + (2 + o(1)) ([log (k)]/k)(nk) as k → ∞, when X is the set of all points in Q(n) of a given weight k + 1, provided (k2/[log (k)])1 + 1/k ≤ n.
NP‐completeness of deciding L(n,X) even when every point of X has weight at most 2.
Distance‐constrained multifacility minimax location problems on tree networks
Authors: Erkut E. , Francis R. L. , Tamir A. 
Published: May 2007

AbstractWe consider the problem of locating new facilities with respect to existing facilities on a tree network. The objective is to minimize the maximum of the weighted distances between existing and new facilities and between pairs of new facilities. There are upper bounds on the distances between pairs of new facilities and between new and existing facilities. We give a polynomial order, binary search algorithm, based on rational representation of data. We also present a strongly polynomial order algorithm employing a parameteric approach and exploiting parallelism.
The n‐line traveling salesman problem
Authors: Rote Günter 
Published: May 2007

AbstractThe special case of the Euclidean traveling salesman problem, where the n given points lie on a small number (N) of parallel lines in the plane, is solved by a dynamic programming approach in time nN, for fixed N, i.e., in polynomial time. This extends a result of Cutler (1980) for three lines. Such problems arise, for example, in the fabrication of printed circuit boards, where the distance traveled by a laser that drills holes in certain places of the board should be minimized. The parallelity condition can be relaxed to point sets that lie on N “almost parallel” line segments. We give a characterization of the allowed segment configurations by a set of forbidden subconfigurations.
On the optimal strongly connected orientations of city street graphs. III. Three east–west avenues or north–south streets
Authors: Roberts Fred S. , Xu Yonghua 
Published: May 2007

AbstractWe consider strongly connected orientations of the grid graph which has n1 + 1 eastwest avenues and n2 + 1 north–south streets. We seek optimal strongly connected orientations according to several different definitions of optimality. In earlier work, such optimal orientations were found for n1, n2 both at least 4 and for n1 = 1. Here we consider the case n1 = 2.
Financial flow of funds networks
Authors: Nagurney Anna , Hughes Merritt 
Published: May 2007

AbstractThis article develops a general network model of financial flow of funds accounting that explicitly incorporates feedback and can be used to calculate reconciled values of all outstanding financial instruments, tangible assets, and net worth. The model captures, as special cases, distinct data‐specific problem scenarios and permits the estimation of sector holdings of both assets and liabilities, total outstanding instrument volumes, and total sector holdings. A decomposition algorithm is then proposed that resolves the network problem into simpler network subproblems, each of which can then be solved exactly in closed form. The algorithm is applied to a dataset derived from the Federal Reserve Board data for 1989. The reconciled dataset can then be used as a base line for an empirical general equlibrium model and for macromonetary policy analysis.
Optimal routing and process scheduling for a mobile service facility
Authors: Akinc Umit , Srikanth Kizhanatham 
Published: May 2007

AbstractThis paper deals with the problem of delivering a well‐defined service to a given set of points efficiently. Efficiencies are sought through providing the services by use of a mobile service unit (MSU). The service facility is mobile in the sense that it can move from point to point at some “move” cost. Unlike the traveling salesman‐type problems however the present problem does not require a physical visit to every point for servicing. Points can be serviced from a distance, while the facility is stationed at a nearby point, at some “processing” cost that may depend on many factors, including the distance involved. The problem is to find the subset and the sequence of nodes that the mobile service unit should physically visit and the set of other points it should service while at each of these visited nodes so as to minimize the sum of move and processing costs. A Lagrangean‐based branch‐and‐bound algorithm is proposed. This algorithm is aided by a powerful upper‐boundig routine and sensitivity tests and logical dominance rules to fix zero/one variables. Somewhat encouraging computational results are presented.
A routing algorithm for virtual circuit data networks with multiple sessions per O—D pair
Authors: Yee James R. , Lin Frank Y. S. 
Published: May 2007

AbstractIn virtual circuit networks, all the packets in a session are transmitted over exactly one path established between the origin and the destination. For each origin–destination pair, it is assumed that there are multiple sessions. We consider the problem of choosing a path for each session so as to minimize the average packet delay in the network. We formulate this problem as a nonlinear multicommodity flow problem with integer decision variables. An iterative scheme that is similar to local search is developed to solve this problem. In each iteration, we apply Lagrangean relaxation and a multiplier adjustment procedure to solve a restricted problem. We show that the Lagrangean dual problem can be solved exactly by solving a convex program. In computational experiments, our algorithm determines solutions that are within 1% of an optimal solution in minutes of CPU time for networks with 26–61 nodes. In addition, we show that our proposed algorithm is better both theoretically and computationally than K(0)‐ordering, single‐path routing, or round‐off Frank–Wolfe heuristics.
A reliability‐improving graph transformation with applications to network reliability
Authors: Satyanarayana A. , Schoppmann L. , Suffel C. L. 
Published: May 2007

AbstractThis paper considers a probabilistic graph in which the points are perfectly reliable but the edges operate independently of one another, all with some known probability p. The graph G is in an operating state if the surviving edges induce a spanning connected subgraph of G. The all‐terminal reliability R(G,p) of G is the probability that G is in an operating state. A graph transformation, called “the swing surgery,” is introduced, and it is shown that this surgery has important properties. First, if H is the graph obtained by deleting m independent edges from the complete graph, then for any other graph G with the same number of points and edges as H, R(H,p) > R(G,p) for all 0 < p < 1. Moreover, the swing surgery yields a simple topological proof of the well‐known result that H has more spanning trees than does G. Another important consequence is that given any graph G there exists a threshold graph T with the same number of points and edges as G such that R(T,p) ≤ R(G,p) for all 0 < p < 1.
The generalized P‐forest problem on a tree network
Authors: Tamir Arie , Lowe Timothy J. 
Published: May 2007

AbstractIn two recent papers, similar multifacility problems on tree networks were studied where facilities are subtrees of the tree. The complexity of the problems was left as open. In this paper, we formulate a general model that includes the above‐cited problems as special cases and give a polynomial algorithm to solve the general model.
Complexity results for well‐covered graphs
Authors: Sankaranarayana Ramesh S. , Stewart Lorna K. 
Published: May 2007

AbstractA graph with n vertices is well covered if every maximal independent set is a maximum independent set and very well covered if every maximal independent set has size n/2. In this work, we study these graphs from an algorithmic complexity point of view. We show that well‐covered graph recognition is co‐NP‐complete and that several other problems are NP‐complete for well‐covered graphs. A number of these problems remain NP‐complete on very well covered graphs, while some admit polynomial time solutions for the smaller class. For both families, the isomorphism problem is as hard as general graph isomorphism.
Special cases of traveling salesman and repairman problems with time windows
Authors: Tsitsiklis John N. 
Published: May 2007

AbstractConsider a complete directed graph in which each arc has a given length. There is a set of jobs, each job i located at some node of the graph, with an associated processing time hi, and whose execution has to start within a presepecified time window [ri, di]. We have a single server that can move on the arcs of the graph, at unit speed, and that has to execute all of the jobs within their respective time windows. We consider the following two problems: (a) minimize the time by which all jobs are executed (traveling salesman problem) and (b) minimize the sum of the waiting times of the jobs (traveling repairman problem). We focus on the following two special cases: (a) The jobs are located on a line and (b) the number of nodes of the graph is bounded by some integer constant B. Furthermore, we consider in detail the special cases where (a) all of the processing times are 0, (b) all of the release times ri are 0, and (c) all of the deadlines di are infinite. For many of the resulting problem combinations, we settle their complexity either by establishing NP‐completeness or by presenting polynomial (or pseudopolynomial) time algorithms. Finally, we derive algorithms for the case where, for any time t, the number of jobs that can be executed at that time is bounded.
On a parametric shortest path problem from primal—dual multicommodity network optimization
Authors: Polak George G. 
Published: May 2007

AbstractEach iteration of the primal—dual linear programming algorithm entails a dual update. For the maximal multicommodity flow problem, and for multicommodity network synthesis, that requires finding a breakpoint in a parametric all pairs' shortest path problem. A procedure based on the Floyd—Warshall Algorithm solves this problem in polynomial (cubic in the number of nodes) time.
The optimal partitioning of networks
Authors: Cheng Chung‐Kuan 
Published: May 2007

AbstractThe work proposes several partitioning criteria, i.e, the flux cutA, the flux cutB, the cost ratio cut, and one generalized minimum cut. The flux cutBis an extension of the flux cutA. The cost ratio cut generates an optimal partitioning for a linear placement problem. The generalized minimum cut uses a cost function related to a polynomial function of the sizes of two partitioned subsets. A high‐order polynomial function tends to generate partitions such that the partitioned subsets equal specified sizes. A simplified case is the ratio cut that is shown to derive the clustering structure of the network. The physical meaning of the cuts is described. The partitioning problems are shown to be strongly related to the communication problems. Several network flow models are constructed. We illustrate relations between the maximum flow solutions and the minimum partitionings. We use linear programming to formulate the proposed maximum flow problems. The duality techniques of linear programming are utilized to derive a relation to the optimal partition solution. Thus, we have identified the cases when the optimal partition solutions can be determined in polynomial time.
Sequential information dissemination by packets
Authors: Bagchi A. , Schmeichel E. F. , Hakimi S. L. 
Published: May 2007

AbstractConsider a network consisting of units and links that connect pairs of units. Suppose each of the units possesses a unique message that is to be received by all other units. This is called gossiping. A related problem is that of census taking in which a particular unit has to receive every other unit's message. We study gossiping and census taking in a network in which the units communicate by transmitting packets of a fixed size, so that only a bounded number of messages can be sent in a single transmission. We also discuss the complexity of gossiping when the messages are of different sizes.
Paths through a maze of rectangles
Authors: Coffman E. G. , Gilbert E. N. 
Published: May 2007

AbstractFinding short paths through mazes of rectangles has applications in VLSI wire‐routing and robotics. This paper introduces and analyzes heuristic algorithms for finding short paths, under the assumption that the algorithms have no information about rectangles not already encountered along a path. Tight worst‐case bounds are derived for the ratio of the length of these algorithms' paths to the lengths of shortest paths. A model of random mazes is defined for testing the typical or average‐case behavior of algorithms. Although specially designed mazes can force the heuristic algorithms to give long paths, simulations and analysis show that the better heuristics usually give paths nearly as short as possible.
Algorithms for K‐terminal reliability problems with node failures
Authors: Elmallah Ehab S. 
Published: May 2007

AbstractConsider a distributed processing system with a set K of sites that can either cooperate in computing a function or hold resources required by other sites. The system is implemented using a communication network with unreliable nodes. Two simplified reliability problems then arise. In the first problem, we are interested in computing the probability that every operational pair of sites in K can communicate with each other. This problem is known to be #P‐complete. In the second problem, the sites in K are service centers. Our reliability measure is the probability that every operational site in the network is connected to at least one operational service center. In this paper, we define the class of t‐polygon graphs, t ≥ 3, as the intersection graphs of straight‐line chords in a convex t‐gon. Hence, any t‐polygon graph is a circle graph. We show that both problems admit polynomial time solutions when the underlying graph of the network is restricted to a t‐polygon graph, for a fixed t.
Cell suppression: Disclosure protection for sensitive tabular data
Authors: Kelly James P. , Golden Bruce L. , Assad Arjang A. 
Published: May 2007

AbstractWhen a statistical agency, such as the United States Bureau of the Census, publishes tabular data, it must withhold certain data elements that contain confidential information associated with the data respondents. Cell suppression is a technique commonly used in the publishing of economic data in tabular formats. The sensitive entries, which are called primary suppressions, need to be suppressed. However, the suppression of the primary cells alone still allows one to estimate a range for each of the missing values by considering the published entries. Additional entries in the table must be suppressed to ensure that these ranges are not too narrow. Traditionally, the protection required is defined by an interval centered around the value of each primary suppression. This paper formulates and develops solution techniques for the traditional problem as well as for a relaxation of the problem where sliding protection ranges are allowed. In the relaxed problem, the protection ranges have fixed widths but are free to slide; the only restriction is that each range must contain the value of the primary suppression. We present network flow‐based heuristics for both versions of the cell suppression problem and use a lower‐bounding procedure to evaluate the performance of the heuristics. Extensive computational results based on real‐world and randomly generated tables demonstrate that sliding protection ranges can significantly reduce the total amount of suppressed data, as compared to the traditional suppression scheme. Furthermore, the heuristics produce optimal or near‐optimal solutions for real‐world problems.
On a leverage problem in the hypercube
Authors: Hamburger Peter , Pippert Raymond E. , Douglas Weakley W. 
Published: May 2007

AbstractThe leverage of a set S of elements (vertices and edges) of a graph G, with respect to a graphical parameter P, is the change induced in P by the removal of S. We consider the case in which G is a hypercube and P is the sum of the distances between vertices. The determination of the minimum leverage of any set of k edges leads to the question of the existence of a perfect matching in which no two edges lie on a 4‐cycle. We give a constructive proof of the existence of such a matching and note additional interesting problems.
Reliable communication in networks with Byzantine link failures
Authors: Pelc Andrzej 
Published: May 2007

AbstractWe consider the problem of communication between nodes of a network whose links are subject to arbitrary failures: A failed link may not only stop transmitting messages but may corrupt them in any possible way. We characterize networks allowing communication in spite of at most t failures. Also, for every fixed link failure probability p ≤ .29, we construct a class of networks for which the probability of successful communication converges to 1 as the number of nodes grows. It is shown that the number of links in these networks is asymptotically smallest possible to assure reliable communication. Moreover, in these networks, communication can be completed in just two information exchange rounds. Finally, we give a protocol assuring reliable communication in the hypercube if link failure probability is p ≤ .02 and show that no such protocol exists if p ≥ .15.
Finding all minimum‐cost perfect matchings in Bipartite graphs
Authors: Fukuda Komei , Matsui Tomomi 
Published: May 2007

AbstractThe Hungarian method is an efficient algorithm for finding a minimal‐cost perfect matching in a weighted bipartite graph. This paper describes an efficient algorithm for finding all minimal‐cost perfect matchings. The computational time required to generate each additional perfect matching is O(n(n + m)), and it requires O(n + m) memory storage. This problem can be solved by algorithms for finding the Kth‐best solution of assignment problems. However, the memory storage required by the known algorithms grows in proportion to K, and, hence, it may grow exponentially in n. So, our specialized algorithm has a considerable advantage in memory requirement over the precious more general algorithms for Kth‐best assignment problems. Here we will show that the enumeration of all minimal‐cost perfect matchings can be reduced to the enumeration of all perfect matchings in some bipartite graph. Therefore, our algorithm can be seen as an algorithm for enumerating all perfect matchings in a given bipartite graph.
Tighter time bounds on fault‐tolerant broadcasting and gossiping
Authors: Gargano Luisa 
Published: May 2007

AbstractConsider a network in which n processors are connected by unreliable lines and are allowed to communicate with at most one other processor at a time. In this paper, the problems of broadcasting and gossiping are considered. Broadcast is the task of transmitting a message, originated at one node, to all other nodes in the network. Gossiping refers to the process of information dissemination when each processor knows a unique item of information and must transmit it to all the other processors in the network. In this paper, new bounds on fault‐tolerant broadcasting and gossiping times are obtained. The given bounds improve on previously known results. In particular, if n is a power of two, the given broadcast and gossiping schemes require minimum time and are supported by a network having the minimum possible number of edges.
A pseudopolynomial network flow formulation for exact knapsack separation
Authors: Andrew Boyd E. 
Published: May 2007

AbstractThe NP‐complete separation problem for the knapsack polyhedron 𝓅 is formulated as a side‐constrained network flow problem with a pseudopolynomial number of vertices and edges. It is demonstrated that the primal polyhedron associated with this formulation can be projected onto an appropriate subspace to yield 𝓅 and that the dual polyhedron can be projected onto an appropriate subspace to yield the polar of 𝓅. Practical consequences of the formulation are discussed.
On a tree‐shaped facility location problem of Minieka
Authors: Rabinovitch Ramon , Tamir Arie 
Published: May 2007

AbstractMinieka and Hakimi et al. considered the problem of locating a tree‐shaped facility of a given length in a tree network, with the objective of maximizing the sum of node distances from this facility. They stated the complexity of the model as an open problem. We prove that it is NP‐complete and provide a pseudopolynomial time algorithm.
Parallel contractions of grids for task assignment to processor networks
Authors: Ben‐Natan Ron , Barak Amnon 
Published: May 2007

AbstractLetGbe a simple connected undirected graph. A contraction φ ofGis a mapping fromG=G(V, E)toG'=G'(V', E'), whereG'is also a simple connected undirected graph, such that ifu, vφV(G)are connected by an edge (adjacent) inG, then either φ(u)= φ(v) orφ(u)and φ(v)are adjacent inG'. Consider a family of contractions, called bounded contractions, in which ∀v'∈V', the degree ofv'inG', DegG'(v'), satisfiesDegG'(v')≤ |φ−1(v')|, where φ−1(v')denotes the set of vertices inGmapped tov'under φ. These types of contractions are useful in the assignment (mapping) of parallel programs to a network of interconnected processors, where the number of communication channels of each processor is small. In this paper, we are concerned with bounded contractions of two‐dimensional grids such as mesh, hexagonal, and triangular arrays. For each of these graphs, we give contraction schemes that yield mappings of the minimal possible degree, such that the topology of the resulting graphs is identical to that of the desired target graph. We also prove that some contractions are not possible, regardless of their degree.