Arrow Research search

Author name cluster

C. Greg Plaxton

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.

21 papers
2 author rows

Possible papers

21

SODA Conference 2019 Conference Paper

A (1 + 1/e)-Approximation Algorithm for Maximum Stable Matching with One-Sided Ties and Incomplete Lists

  • Chi-Kit Lam
  • C. Greg Plaxton

We study the problem of finding large weakly stable matchings when preference lists are incomplete and contain one-sided ties. Computing maximum weakly stable matchings is known to be NP-hard. We present a polynomial-time algorithm that achieves an improved approximation ratio of 1 + 1/ e. Like a number of existing approximation algorithms for this problem, our algorithm is based on a proposal process in which numerical priorities are adjusted according to the solution of a linear program, and are used for tiebreaking purposes. Our main idea is to use an infinitesimally small step size for incrementing the priorities. Our analysis involves solving an infinite-dimensional factor-revealing linear program. We also show that the ratio 1 + 1/e is an upper bound for the integrality gap, which matches the known lower bound.

Details

STOC Conference 2003 Conference Paper

Approximation algorithms for hierarchical location problems

  • C. Greg Plaxton

We formulate and (approximately) solve hierarchical versions of two prototypical problems in discrete location theory, namely, the metric uncapacitated k -median and facility location problems. Our work yields new insights into hierarchical clustering, a widely used technique in data analysis. First, we show that every metric space admits a hierarchical clustering that is within a constant factor of optimal at every level of granularity with respect to the average (squared) distance objective. Second, we provide a natural solution to the leaf ordering problem encountered in the traditional dendrogram-based approach to the visualization of hierarchical clusterings.

Details

UAI Conference 2002 Conference Paper

Optimal Time Bounds for Approximate Clustering

  • Ramgopal Mettu
  • C. Greg Plaxton

Clustering is a fundamental problem in unsupervised learning, and has been studied widely both as a problem of learning mixture models and as an optimization problem. In this paper, we study clustering with respect the emph{k-median} objective function, a natural formulation of clustering in which we attempt to minimize the average distance to cluster centers. One of the main contributions of this paper is a simple but powerful sampling technique that we call emph{successive sampling} that could be of independent interest. We show that our sampling procedure can rapidly identify a small set of points (of size just O(klog{n/k})) that summarize the input points for the purpose of clustering. Using successive sampling, we develop an algorithm for the k-median problem that runs in O(nk) time for a wide range of values of k and is guaranteed, with high probability, to return a solution with cost at most a constant factor times optimal. We also establish a lower bound of Omega(nk) on any randomized constant-factor approximation algorithm for the k-median problem that succeeds with even a negligible (say 1/100) probability. Thus we establish a tight time bound of Theta(nk) for the k-median problem for a wide range of values of k. The best previous upper bound for the problem was O(nk), where the O-notation hides polylogarithmic factors in n and k. The best previous lower bound of O(nk) applied only to deterministic k-median algorithms. While we focus our presentation on the k-median objective, all our upper bounds are valid for the k-means objective as well. In this context our algorithm compares favorably to the widely used k-means heuristic, which requires O(nk) time for just one iteration and provides no useful approximation guarantees.

Details

FOCS Conference 2000 Conference Paper

The Online Median Problem

  • Ramgopal Mettu
  • C. Greg Plaxton

We introduce a natural variant of the (metric uncapacitated) k-median problem that we call the online median problem. Whereas the k-median problem involves optimizing the simultaneous placement of k facilities, the on-line median problem imposes the following additional constraints: the facilities are placed one at a time; a facility cannot be moved once it is placed, and the total number of facilities to be placed, k, is not known in advance. The objective of an online median algorithm is to minimize the competitive ratio, that is, the worst-case ratio of the cost of an online placement to that of an optimal offline placement. Our main result is a linear-time constant-competitive algorithm for the online median problem. In addition, we present a related, though substantially simpler linear-time constant-factor approximation algorithm for the (metric uncapacitated) facility location problem. The latter algorithm is similar in spirit to the recent primal-dual-based facility location algorithm of Jain and Vazirani, but our approach is more elementary and yields an improved running time.

Details

FOCS Conference 1996 Conference Paper

Fast Fault-Tolerant Concurrent Access to Shared Objects

  • C. Greg Plaxton
  • Rajmohan Rajaraman

The authors consider a synchronous model of distributed computation in which n nodes communicate via point-to-point messages, subject to the following constraints: (i) in a single "step", a node can only send or receive O(logn) words, and (ii) communication is unreliable in that a constant fraction of all messages are lost at each step due to node and/or link failures. They design and analyze a simple local protocol for providing fast concurrent access to shared objects in this faulty network environment. In the protocol, clients use a hashing-based method to access shared objects. When a large number of clients attempt to read a given object at the same time, the object is rapidly replicated to an appropriate number of servers. Once the necessary level of replication has been achieved, each remaining request for the object is serviced within O(1) expected steps. The protocol has practical potential for supporting high levels of concurrency in distributed file systems over wide area networks.

Details

FOCS Conference 1995 Conference Paper

Tight Bounds for a Distributed Selection Game with Applications to Fixed-Connection Machines

  • C. Greg Plaxton

We define a distributed selection game that generalizes a selection problem considered by S. R. Kosaraju (1989). We offer a tight analysis of our distributed selection game, and show that the lower bound for this abstract communication game directly implies near-tight lower bounds for certain selection problems on fixed-connection machines. For example, we prove that any deterministic comparison-based selection algorithm on an (n/log n)-processor bounded-degree hypercubic machine requires /spl Omega/(log/sup 3/2/n) steps in the worst case. This lower bound implies a non-trivial separation between the power of bounded-degree hypercubic and expander-based machines. Furthermore, we show that the algorithm underlying our tight upper bound for the distributed selection game can be adapted to run in O((log/sup 3/2/n) (log log n)/sup 2/) steps on any (n/log n)-processor hypercubic machine.

Details

FOCS Conference 1992 Conference Paper

Improved Lower Bounds for Shellsort

  • C. Greg Plaxton
  • Bjorn Poonen
  • Torsten Suel

The authors give improved lower bounds for Shellsort based on a new and relatively simple proof idea. The lower bounds obtained are both stronger and more general than the previously known bounds. In particular, they hold for nonmonotone increment sequences and adaptive Shellsort algorithms, as well as for some recently proposed variations of Shellsort. >

Details

FOCS Conference 1991 Conference Paper

Highly Fault-Tolerant Sorting Circuits

  • Frank Thomson Leighton
  • Yuan Ma
  • C. Greg Plaxton

The problem of constructing a sorting circuit that will work well even if a constant fraction of its comparators fail at random is addressed. Two types of comparator failure are considered: passive failures, which result in no comparison being made (i. e. , the items being compared are output in the same order that they are input), and destructive failures, which result in the items being output in the reverse of the correct order. In either scenario, it is assumed that each comparator is faulty with some constant probability rho, and a circuit is said to be fault-tolerant if it performs some desired function with high probability given that each comparator fails with probability rho. One passive and two destructive circuits are constructed. >

Details

FOCS Conference 1990 Conference Paper

A (fairly) Simple Circuit that (usually) Sorts

  • Frank Thomson Leighton
  • C. Greg Plaxton

A natural k-round tournament over n=2/sup k/ players is analyzed, and it is demonstrated that the tournament possesses a surprisingly strong ranking property. The ranking property of this tournament is exploited by being used as a building block for efficient parallel sorting algorithms under a variety of different models of computation. Three important applications are provided. First, a sorting circuit of depth 7. 44 log n, which sorts all but a superpolynomially small fraction of the n-factorial possible input permutations, is defined. Secondly, a randomized sorting algorithm that runs in O(log n) word steps with very high probability is given for the hypercube and related parallel computers (the butterfly, cube-connected cycles, and shuffle-exchange). Thirdly, a randomized algorithm that runs in O(m+log n)-bit steps with very high probability is given for sorting n O(m)-bit records on an n log n-node butterfly. >

Details

FOCS Conference 1989 Conference Paper

On the Network Complexity of Selection

  • C. Greg Plaxton

The sequential complexity of determining the kth largest out of a given set of n keys is known to be linear. Thus, given a p-processor parallel machine, it is asked whether or not an O(n/p) selection algorithm can be devised for that machine. An Omega ((n/p) log log p+log p) lower bound is obtained for selection on any network that satisfies a particular low expansion property. The class of networks satisfying this property includes all of the common network families, such as the tree, multidimensional mesh, hypercube, butterfly, and shuffle-exchange. When n/p is sufficiently large (e. g. greater than log/sup 2/p on the butterfly, hypercube, and shuffle-exchange), this result is matched by the upper bound given previously by the author (Proc. 1st Ann. ACM Symp. on Parallel Algorithms and Architecture p. 64-73, 1989). >

Details