A number of network path delay, loss, or bandwidth inference mechanisms have been proposed over the past decade. Concurrently, several network measurement services have been deployed over the Internet and intranets. We consider inference mechanisms that use O(n) end-to-end measurements to predict the O(n2) end-to-end pairwise measurements among n nodes, and investigate when it is beneficial to use them in measurement services. In particular, we address the following questions : 1) For which measurement request patterns would using an inference mechanism be advantageous? 2) How does a measurement service determine the set of hosts that should utilize inference mechanisms, as opposed to those that are better served using direct end-to-end measurements? We explore three solutions that identify groups of hosts which are likely to benefit from inference. We compare these solutions in terms of effectiveness and algorithmic complexity. Results with synthetic data sets and data sets from a popular peer-to-peer system demonstrate that our techniques accurately identify host subsets that benefit from inference, in significantly less time than an algorithm that identifies optimal subsets. The measurement savings are large when measurement request patterns exhibit small-world characteristics, which is often the case. (Part of this work (focusing on one of three solutions presented in this paper) appeared in).

A number of network path delay, loss, or bandwidth inference mechanisms have been proposed over the past decade. Concurrently, several network measurement services have been deployed over the Internet and intranets. We consider inference mechanisms that use O(n) end-to-end measurements to predict the O(n2) end-to-end pairwise measurements among n nodes, and investigate when it is beneficial to use them in measurement services. In particular, we address the following questions: (1) For which measurement request patterns would using an inference mechanism be advantageous? (2) How does a measurement service determine the set of hosts that should utilize inference mechanisms, as opposed to those that are better served using direct end-to-end measurements? (3) How can the answer to question 2 be efficiently computed as measurement requests arrive and terminate? Our solution is able to identify groups of hosts which are likely to benefit from inference, by utilizing a probabilistically generated spanning forest on the measurement request graph. We compare our solution to a simple heuristic that uses the number of measurements a host participates in. Results with synthetic datasets as well as datasets from a popular peer-to-peer system demonstrate that our technique identifies host subsets that benefit from inference quite accurately, and in significantly less time than an algorithm that identifies optimal subsets. The measurement savings are large when measurement request patterns exhibit small-world characteristics, which is often the case for peer-to-peer and other popular distributed systems.

Ambivalent data structures are presented for several problems on undirected graphs. These data structures are used in finding the k smallest spanning trees of a weighted undirected graph in $O(m \log \beta (m,n) + \min \{ k^{3/2}, km^{1/2} \} )$ time, where m is the number of edges and n the number of vertices in the graph. The techniques are extended to find the k smallest spanning trees in an embedded planar graph in $O(n + k (\log n)^3 )$ time. Ambivalent data structures are also used to dynamically maintain 2-edge-connectivity information. Edges and vertices can be inserted or deleted in $O(m^{1/2})$ time, and a query as to whether two vertices are in the same 2-edge-connected component can be answered in $O(\log n)$ time, where m and n are understood to be the current number of edges and vertices, respectively.

The problem of scheduling n unit-time jobs with real-valued release times and deadlines is shown to be in NC. The solution is based on characterizations of a canonical schedule and best subset of jobs to be scheduled in a given time interval. The algorithm runs on a CREW PRAM in $O((\log n)^2 )$ time and uses $O({{n^4 } / {\log n}})$ processors.

Consider the problem of using a vehicle to transport k objects one at a time between s stations on a circular track. Let the cost of the transportation be the total distance traveled by the vehicle on the track. An $O(k + M(s,q))$ time algorithm is presented to find a minimum cost transportation, where $M(m,n)$ is the time to solve a minimum spanning tree problem on a graph with m edges and n vertices, and $q \leqslant \min \{ {k,s} \}$ is the number of strongly connected components in an associated balanced problem. Also, the minimum spanning tree problem on a graph with m edges and n vertices is reduced to a transportation problem on a linear track with $O(m)$ stations, $O(m)$ objects, and $O(n)$ strongly connected components in $O(m)$ time.

Consider the problem of finding a minimum cost tour to transport a set of objects between the vertices of a tree by a vehicle that travels along the edges of the tree. The vehicle can carry only one object at a time, and it starts and finishes at the same vertex of the tree. It is shown that if objects can be dropped at intermediate vertices along its route and picked up later, then the problem can be solved in polynomial time. Two efficient algorithms are presented for this problem. The first algorithm runs in $O(k + qn)$ time, where n is the number of vertices in the tree, k is the number of objects to be moved, and $q \leq \min \{ k,n \}$ is the number of nontrivial connected components in a related directed graph. The second algorithm runs in $O(k + n\log n)$ time.

Ambivalent data structures are presented for several problems on undirected graphs. They are used in finding the k smallest spanning trees of a weighted undirected graph in O(m log beta (m,n)+min(k/sup 3/2/, km/sup 1/2/)) time, where m is the number of edges and n the number of vertices in the graph. The techniques are extended to find the k smallest spanning trees in an embedded planar graph in O(n+k(log n)/sup 3/) time. Ambivalent data structures are also used to maintain dynamically 2-edge-connectivity information. Edges and vertices can be inserted or deleted in O(m/sup 1/2/) time, and a query as to whether two vertices are in the same 2-edge-connected component can be answered in O(log n) time, where m and n are understood to be the current number of edges and vertices, respectively. Again, the techniques are extended to maintain an embedded planar graph so that edges and vertices can be inserted or deleted in O((log n)/sup 3/) time, and a query answered in O(log n) time.>

An algorithm is presented for generating a succinct encoding of all pairs shortest path information in a directed planar graph G with real-valued edge costs but no negative cycles. The algorithm runs in O ( pn ) time, where n is the number of vertices in G , and p is the minimum cardinality of a subset of the faces that cover all vertices, taken over all planar embeddings of G . The algorithm is based on a decomposition of the graph into O ( pn ) outerplanar subgraphs satisfying certain separator properties. Linear-time algorithms are presented for various subproblems including that of finding an appropriate embedding of G and a corresponding face-on-vertex covering of cardinality O ( p ), and of generating all pairs shortest path information in a directed outerplannar graph.

An O(k)-time algorithm is presented for selecting the k-th smallest element in a binary heap of size n >> k.The result matches the information theoretic lower bound, settles an open problem, and contradicts a recently reported lower bound.

The problem of routing messages along near-shortest paths in a distributed network without using complete routing tables is considered. It is assumed that the nodes of the network can be assigned suitable short names at the time the network is established. Two space-efficient near- shortest path routing schemes are given for any class of networks whose members can be decomposed recursively by a separator of size at most a constant c, where $c \geqslant 2$. For an n-node network, the first scheme uses a total of $O(cn \log n)$ items of routing information, each $O(\log n)$ bits long, and $O(\log n)$-bit names, generated from a separator-based decomposition of the network, to achieve routings that are at most three times longer than shortest routings in worst case.l The second scheme augments the node names with $O(c \log c \log n)$ additional bits and uses this to reduce the bound on the routings to $(2 / \alpha) + 1$, where $\alpha, 1 < \alpha \leq 2$, is the root of the equation $\alpha ^{\lceil (c+1) / 2\rceil } - \alpha - 2 = 0$. For both schemes, the node names and the routing information can be determined efficiently.

Previous article Full AccessErratum: Generalized Selection and Ranking: Sorted MatricesGreg N. Frederickson and Donald B. JohnsonGreg N. Frederickson and Donald B. Johnsonhttps://doi.org/10.1137/0219013PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAbout"Erratum: Generalized Selection and Ranking: Sorted Matrices." SIAM Journal on Computing, 19(1), pp. 205–206[1] Greg N. Frederickson and , Donald B. Johnson, Generalized selection and ranking: sorted matrices, SIAM J. Comput., 13 (1984), 14–30 10.1137/0213002 85c:68025 LinkISIGoogle Scholar Previous article FiguresRelatedReferencesCited byDetails Scheduling with gaps: new models and algorithms21 July 2021 | Journal of Scheduling, Vol. 24, No. 4 Cross Ref Geometric clusteringACM Transactions on Algorithms, Vol. 7, No. 4 Cross Ref Cache-oblivious selection in sorted matricesInformation Processing Letters, Vol. 109, No. 2 Cross Ref Volume 19, Issue 1| 1990SIAM Journal on Computing History Submitted:10 October 1989Accepted:16 October 1989Published online:31 July 2006 InformationCopyright © 1990 © Society for Industrial and Applied MathematicsPDF Download Article & Publication DataArticle DOI:10.1137/0219013Article page range:pp. 205-206ISSN (print):0097-5397ISSN (online):1095-7111Publisher:Society for Industrial and Applied Mathematics

An algorithm for generating a succinct encoding of all-pairs shortest path information in an n-vertex directed planar G with O(n) edges is presented. The edges have real-valued costs, but the graph contains no negative cycles. The time complexity is given in terms of a topological embedding measure defined in the paper. The algorithm uses a decomposition of the graph into outerplanar subgraphs satisfying certain separator properties, and a linear-time algorithm is presented to find this decomposition.>

The problem of transporting a set of objects between the vertices of a tree by a unit capacity vehicle that travels along the edges of the tree is considered. For the case in which any object can be dropped at intermediate vertices along its route and picked up later, the authors present algorithms for finding a minimum cost transportation that run in O(k+qn) time and in O(k+n log n) time, where n is the number of vertices in the tree, k is the number of objects to be moved, and q>

The problem of routing messages along near-shortest paths in a distributed network without using complete routing tables is considered. It is assumed that the nodes of the network can be assigned suitable short names at the time the network is established. Two space-efficient near-shortest-path routing schemes are given for the class of planar networks. Both schemes use the separator property of planar networks in assigning the node names and performing the routings. For an n-node network, the first scheme uses $O(\log n)$-bit names and a total of $O(n^{{4 / 3}} )$ items of routing information, each $O(\log n)$ bits long, to generate routings that are only three times longer than corresponding shortest routings in worst cases. For any constant $\epsilon ,0 < \epsilon < 1/3$, the second scheme achieves the better space bound of $O(n^{1 + \epsilon } )$ items, each $O(({1 / \epsilon })\log n)$ bits long, but at the expense of $O(({1 / \epsilon })\log n)$-bit node names and a worst-case bound of 7 on the routings.

Consider a matroid of rank n in which each element has a real-valued cost and one of $d > 1$ colors. A class of matroid intersection problems is studied in which one of the matroids is a partition matroid that specifies that a base has $q_j $ elements of color j, for $j = 1,2, \cdots ,d$. Relationships are characterized among the solutions to the family of problems generated when the vector $(q_1 ,q_2 , \cdots ,q_d )$ is allowed to range over all values that sum to n. A fast algorithm is given for solving such matroid intersection problems when d is small. A characterization is presented for how the solution changes when one element changes in cost. Data structures are given for updating the solution on-line each time the cost of an arbitrary matroid element is modified. Efficient update algorithms are given for maintaining a color-constrained minimum spanning tree in either a general or a planar graph. An application of the techniques to the problem of finding a minimum spanning tree with several degree-constrained vertices is described.

The problem of designing space- and communication-efficient routing schemes for networks that experience faults is addressed. For any outerplanar network containing t faults, a succinct routing scheme is presented that uses O( alpha tn) space and communication to generate routings that are less than (( alpha +1)/( alpha -1))/sup t/ times longer than optimal, where alpha >1 is an odd-valued integer parameter. Thus, the routings can be tuned as desired, using a suitable amount of information. Efficient sequential and distributed algorithms are presented for setting up the routing schemes.>

An algorithm is presented for generating a succinct encoding of all pairs shortest path information in a directed planar graph G with real-valued edge costs but no negative cycles. The algorithm runs in Ο(pn) time, where n is the number of vertices in G, and p is the minimum cardinality of a subset of the faces that cover all vertices, taken over all planar embeddings of G. Linear-time algorithms are presented for various subproblems including that of finding an appropriate embedding of G and a corresponding face-on-vertex covering of cardinality Ο(p), and of generating all pairs shortest path information in a directed outerplanar graph.

The problem of electing a leader in a synchronous ring of n processors is considered. Both positive and negative results are obtained. On the one hand, if processor IDS are chosen from some countable set, then there is an algorithm that uses only O ( n ) messages in the worst case. On the other hand, any algorithm that is restricted to use only comparisons of IDs requires Ω( n log n ) messages in the worst case. Alternatively, if the number of rounds is required to be bounded by some t in the worst case, and IDs are chosen from any set having at least ƒ( n, t ) elements, for a certain very fast-growing function ƒ, then any algorithm requires Ω( n log n ) messages in the worst case.

Graph decomposition and data structures techniques are presented that exploit the structure of planar graphs to yield faster algorithms for a number of shortest path and related problems. Improved algorithms are presented for the single source problem, the all pairs problem, the problem of finding a minimum cut in an undirected graph, and testing the feasibility of a multicommodity flow when all sources and sinks are on the same face. The algorithm for the single source takes $O(n\sqrt {\log n} )$ time in an n-vertex graph, an improvement from $O(n\log n)$. The algorithm for all pairs takes $O(n^2 )$ time, an improvement from $O(n^2 \log n)$. The algorithm for minimum cut takes $O(n\log n)$ time, an improvement from $O(n(\log n)^2 )$. As a consequence, an algorithm for maximum flow is similarly improved.

Message routing strategies are given for networks with certain separator properties. These strategies use considerably less space than complete routing tables, keep node names to O(log n) bits, and still route along near-shortest paths. For any network with separators of size at most a small constant c, a total of O(n log n) items of routing information is stored, and any message is routed along a path of length at most (2/α) + 1 times the length of an optimal path, where α ≫ 1 is the positive root of the equation α⌈(c+1)/2⌉ - α - 2 = 0. For planar networks, O(n1+ε) items are stored, for any constant ε, 0 ≪ ε ≪ 1/3, and the length of any message path is at most 7 times that of an optimal path.

Article Free Access Share on Optimal message routing without complete routing tables Authors: Greg N Frederickson Department of Computer Science, Purdue University, West Lafayette, Indiana Department of Computer Science, Purdue University, West Lafayette, IndianaView Profile , Ravi Janardan Department of Computer Science, Purdue University, West Lafayette, Indiana Department of Computer Science, Purdue University, West Lafayette, IndianaView Profile Authors Info & Claims PODC '86: Proceedings of the fifth annual ACM symposium on Principles of distributed computingNovember 1986 Pages 88–97https://doi.org/10.1145/10590.10598Published:01 November 1986Publication History 9citation207DownloadsMetricsTotal Citations9Total Downloads207Last 12 Months7Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Data structures are presented for the problem of maintaining a minimum spanning tree on-line under the operation of updating the cost of some edge in the graph. For the case of a general graph, maintaining the data structure and updating the tree are shown to take $O(\sqrt m )$ time, where m is the number of edges in the graph. For the case of a planar graph, a data structure is presented which supports an update time of $O((\log m)^2 )$. These structures contribute to improved solutions for the on-line connected components problem and the problem of generating the K smallest spanning trees.

We consider the problem of electing a leader in a synchronous ring of n processors. We obtain both positive and negative results.

Matroid intersection problems are considered in which one of the matroids is a partition matroid specifying that exactly q elements in the solution must be red, and the rest green. A characterization is presented for how the solution changes when one element changes in cost. Data structures are given for maintaining the solutions to several such problems online under the operation of changing an edge cost. Efficient update algorithms are given for maintaining a red-green minimum spanning tree in both a general and a planar graph, and a red-green job schedule for unit-time jobs with integer release times and deadlines.

Self-organizing heuristics are presented for data structures containing elements with different weights (access probabilities). The structures use just a constant number of locations in addition to those required for the values of the elements, and support average access times that are within a constant multiplicative factor of optimal. Data structures and corresponding heuristics with essentially optimal average unsuccessful search times are also given for the case in which there are probabilities of access associated with the intervals between consecutive element values.

A more general version of the well-known selection problem is formulated, in which constraints on the input set are allowed. Selection (and also ranking) problems are solved optimally for the broad class of inputs constrained to be collections of matrices with sorted rows and sorted columns.The characterization of problem complexity includes an asymptotically significant dependency on the rank of the solution element.

Graph decomposition and data structures techniques are presented that make possible faster algorithms for shortest paths in planar graphs. Improved algorithms are presented for the single source problem, the all pairs problem, and the problem of finding a minimum cut in an undirected graph.

Algorithms are presented for selecting an element of given rank from a set of elements distributed among the nodes of a network. Network topologies considered are a ring, a mesh, and a complete binary tree. For the ring and the mesh, upper bound tradeoffs are identified between the number of messages transmitted and the total delay due to message transmission. For the tree, an algorithm is presented that uses an asymptotically optimal number of messages.

Data structures are presented for the problem of maintaining a minimum spanning tree on-line under the operation of updating the cost of some edge in the graph. For the case of a general graph, maintaining the data structure and updating the tree are shown to take O((@@@@)m) time, where m is the number of edges in the graph. For the case of a planar graph, a data structure is presented which supports an update time of O ((log m)2).

Several new data structures for dictionaries are presented that use just one location in addition to those required for key values.The structures are generahzations of a rotated sorted list, with the best realizing a search tune of O(log n) and insemon and deletion tunes of O(n ~(log n) 3/2) Structures adapted to allow fast average search times and structures that allow pamal match retrieval on records wRh d keys, d > 1, are also considered.

Several new data structures are presented for dictionaries containing elements with different weights (access probabilities). The structures use just one location in addition to those required for the values of the elements, and support access times that are within a constant multiplicative factor of optimal, in terms of the rank of the weight of the desired element. Self-organizing heuristics are analyzed, in terms of both weights and "near-ranks" of weights. The benefits of additional space are investigated within the context of self-organization and unsuccessful search.

The problems of minimizing the expected makespan and minimizing the expected tic for a finite set of independent tasks with exponential service-time distributions on m ~ 2 it processors are considered.It is shown that a scheduling policy minimizes the expected flow timq only if it is shortest expected processing time tint, and that a policy minimizes the expected make and only if it is longest expected processing time fast.

Graph augmentation problems on a weighted graph involve determining a minimum-cost set of edges to add to a graph to satisfy a specified property, such as biconnectivity, bridge-connectivity or strong connectivity. These augmentation problems are shown to be NP-complete in the restricted case of the graph being initially connected. Approximation algorithms with favorable time complexity are presented and shown to have constant worst-case performance ratios.

Several new data structures for dictionaries are presented that use just one location in addition to those required for key values. The structures are generalizations of a rotated sorted list, with the best realizing a search time of 0(log n) and insert and delete times of 0(n√2/log n(log n)3/2). Similar structures are presented for a dictionary with records containing k≫1 keys, under the operations of search, partial match, insert and delete.

Selection in a set requires time linear in the size of the set when there are no a priori constraints on the total orders possible for the set. Constraints often come for free, however, with sets which arise in applications. Linear time selection [Bl] can be suboptimal for such problems. We therefore generalize the well known selection problem to admit constraints on the input sets, with a view toward settling the complexity issues which arise. The generalization also applies to the other quantile problems of ranking a given element in the input set and verification of the claim that a given element has a specified rank.

Approxtmatton algorithms for several NP-complete edge-covermg routing problems are presented and analyzed m terms of the worst-case ratio of the cost of the obtained solutmn to the cost of the optimum solutton A worst-case bound of 2 is proved for the mixed postman algortthm of Edmonds and Johnson, and a related algorithm for the mixed postman problem is shown also to have a worst-case bound of 2 A mixed strategy approach ts used to obtain a bound of ~ for the mixed postman problem A second mixed strategy algorithm, for the mtxed postman on a planar graph, ~s shown to have a worst-case bound of KEY WORDS AND PHRASES Chinese postman problem, mixed postman problem, rural postman problem, NPcomplete problems, polynomml-tlme approximation algorithm, heunsuc, worst-case performance bound, m,xed strategy CR CATEGORIES 5 25, 5 39, 8 3

Several polynomial time approximation algorithms for some $NP$-complete routing problems are presented, and the worst-case ratios of the cost of the obtained route to that of an optimal are determined. A mixed-strategy heuristic with a bound of 9/5 is presented for the stacker-crane problem (a modified traveling salesman problem). A tour-splitting heuristic is given for k-person variants of the traveling salesman problem, the Chinese postman problem, and the stacker-crane problem, for which a minimax solution is sought. This heuristic has a bound of $e + 1 - 1/k$, where e is the bound for the corresponding 1-person algorithm.

Several polynomial time approximation algorithms for some NP-complete routing problems are presented, and the worst-case ratios of the cost of the obtained route to that of an optimal are determined. A mixed-strategy heuristic with a bound of 9/5 is presented for the Stacker-Crane problem (a modified Traveling Salesman problem). A tour-splitting heuristic is given for k-person variants of the Traveling Salesman problem, the Chinese Postman problem, and the Stacker-Crane problem, for which a minimax solution is sought. This heuristic has a bound of e + 1 - 1/k, where e is the bound for the corresponding 1-person algorithm.