Arrow Research search

Author name cluster

Greg N. Frederickson

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

23 papers
2 author rows

Possible papers

23

TCS Journal 2006 Journal Article

Efficient algorithms for robustness in resource allocation and scheduling problems

  • Greg N. Frederickson
  • Roberto Solis-Oba

The robustness function of an optimization (minimization) problem measures the maximum increase in the value of its optimal solution that can be produced by spending a given amount of resources increasing the values of the elements in its input. We present efficient algorithms for computing the robustness function of resource allocation and scheduling problems that can be modeled with partition and scheduling matroids. For the case of scheduling matroids, we give an O ( m 2 n 2 ) time algorithm for computing a complete description of the robustness function, where m is the number of elements in the matroid and n is its rank. For partition matroids, we give two algorithms: one that computes the complete robustness function in O ( m log m ) time, and other that optimally evaluates the robustness function at only a specified point.

Details DOI

FOCS Conference 1991 Conference Paper

Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees

  • Greg N. Frederickson

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

Details

I&C Journal 1990 Journal Article

A distributed shortest path algorithm for a planar network

  • Greg N. Frederickson

An algorithm is presented for finding a single source shortest path tree in a planar undirected distributed network with nonnegative edge costs. The number of messages used by the algorithm is O(n 5 3 ) on an n-node network. Distributed algorithms are also presented for finding a breath-first spanning tree in general network, for finding a shortest path tree in a general network, for finding a separator of a planar network, and for finding a division of a planar network.

Details DOI

FOCS Conference 1989 Conference Paper

Ensemble Motion Planning in Trees

  • Greg N. Frederickson
  • D. J. Guan

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<or=min(k, n) is the number of nontrivial connected components in a related directed graph. In the case in which each object must be carried directly from its initial vertex to its destination, the problem is NP-hard. The authors present approximation algorithms that run in O(k+n) time with a performance ratio of 3/2 and in O(k+n log beta (n, q)) time with performance ratio of 5/4.

Details

FOCS Conference 1989 Conference Paper

Using Cellular Graph Embeddings in Solving All Pairs Shortest Paths Problems (Preliminary Version)

  • Greg N. Frederickson

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

Details

I&C Journal 1987 Journal Article

On-line updating of solutions to a class of matroid intersection problems

  • Greg N. Frederickson
  • Mandayam A. Srinivas

The class of matroid intersection problems is 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 updating the solution on-line each time the cost of an arbitrary matroid element is modified. 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 deadlines.

Details DOI

FOCS Conference 1986 Conference Paper

Separator-Based Strategies for Efficient Message Routing (Preliminary Version)

  • Greg N. Frederickson
  • Ravi Janardan

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.

Details

TCS Journal 1984 Journal Article

Recursively rotated orders and implicit data structures: A lower bound

  • Greg N. Frederickson

A lower bound is derived for the time required to perform an update in an implicit data structure that is stored in a recursively rotated order. The update is shown to require Ω(2 2logn (log n) 1 2 ) data swaps, where n is the number of elements in the structure. This matches an upper bound derived in an earlier paper (Frederickson, 1983).

Details DOI

FOCS Conference 1983 Conference Paper

Shortest Path Problems in Planar Graphs (Preliminary Version)

  • Greg N. Frederickson

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.

Details

TCS Journal 1982 Journal Article

On the relationship between the biconnectivity augmentation and travelling salesman problems

  • Greg N. Frederickson
  • Joseph Ja'ja'

A strategy for solving the traveling salesman problem is adapted to the problem of finding a biconnected subgraph of a weighted graph whose cost function satisfies the triangle inequality. An approximation algorithm similar to Christofides' algorithm [5] for the traveling salesman problem is shown to possess the same worst-case bound of 3 2 when applied to the biconnectivity augmentation problem. A tight inequality is derived relating the cost of an optimal traveling salesman tour to the cost of an optimal biconnection.

Details DOI

FOCS Conference 1981 Conference Paper

Implicit Data Structures for the Weighted Dictionary Problem (preliminary version)

  • Greg N. Frederickson

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.

Details

STOC Conference 1980 Conference Paper

Generalized Selection and Ranking (Preliminary Version)

  • Greg N. Frederickson
  • Donald B. Johnson 0001

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 [B l ] 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.

Details

FOCS Conference 1980 Conference Paper

Implicit Data Structures with Fast Update (Preliminary Report)

  • Greg N. Frederickson

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.

Details

FOCS Conference 1976 Conference Paper

Approximation Algorithms for some Routing Problems

  • Greg N. Frederickson
  • Matthew S. Hecht
  • Chul E. Kim

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.

Details
v2026.09.13