C. Greg Plaxton

Orcid: 0000-0001-7084-1612

  • University of Texas at Austin, USA

According to our database1, C. Greg Plaxton authored at least 68 papers between 1989 and 2023.

Collaborative distances:
  • Dijkstra number2 of two.
  • Erdős number3 of two.



In proceedings 
PhD thesis 


Online presence:

On csauthors.net:


The obnoxious facility location game with dichotomous preferences.
Theor. Comput. Sci., June, 2023

On the Existence of Three-Dimensional Stable Matchings with Cyclic Preferences.
Theory Comput. Syst., 2022

Maximum Stable Matching with One-Sided Ties of Bounded Length.
Theory Comput. Syst., 2022

Egalitarian Resource Sharing Over Multiple Rounds.
CoRR, 2021

Object Allocation Over a Network of Objects: Mobile Agents with Strict Preferences.
Proceedings of the AAMAS '21: 20th International Conference on Autonomous Agents and Multiagent Systems, 2021

A (1 + 1/e)-Approximation Algorithm for Maximum Stable Matching with One-Sided Ties and Incomplete Lists.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Strategyproof Pareto-Stable Mechanisms for Two-Sided Matching with Indifferences.
CoRR, 2017

Group Strategyproof Pareto-Stable Marriage with Indifferences via the Generalized Assignment Game.
Proceedings of the Algorithmic Game Theory - 10th International Symposium, 2017

Bipartite Matching with Linear Edge Weights.
Proceedings of the 27th International Symposium on Algorithms and Computation, 2016

Scheduling Unit Jobs with a Common Deadline to Minimize the Sum of Weighted Completion Times and Rejection Penalties.
Proceedings of the Algorithms and Computation - 25th International Symposium, 2014

Optimal cover time for a graph-based coupon collector process.
J. Discrete Algorithms, 2013

Vertex-Weighted Matching in Two-Directional Orthogonal Ray Graphs.
Proceedings of the Algorithms and Computation - 24th International Symposium, 2013

Competitive Weighted Matching in Transversal Matroids.
Algorithmica, 2012

Buyer-supplier games: Optimization over the core.
Theor. Comput. Sci., 2011

A dynamic unit-demand auction supporting bid revision.
Proceedings of the 13th International Conference on Electronic Commerce, 2011

Maintaining the Ranch topology.
J. Parallel Distributed Comput., 2010

Online Compression Caching.
Proceedings of the Algorithm Theory, 2008

Fast Scheduling of Weighted Unit Jobs with Release Times and Deadlines.
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Online Aggregation over Trees.
Proceedings of the 21th International Parallel and Distributed Processing Symposium (IPDPS 2007), 2007

Reconfigurable Resource Scheduling with Variable Delay Bounds.
Proceedings of the 21th International Parallel and Distributed Processing Symposium (IPDPS 2007), 2007

Online Hierarchical Cooperative Caching.
Theory Comput. Syst., 2006

Approximation algorithms for hierarchical location problems.
J. Comput. Syst. Sci., 2006

Concurrent Maintenance of Rings.
Distributed Comput., 2006

Efficient adaptive collect using randomization.
Distributed Comput., 2006

Reconfigurable resource scheduling.
Proceedings of the SPAA 2006: Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures, Cambridge, Massachusetts, USA, July 30, 2006

Optimal Time Bounds for Approximate Clustering.
Mach. Learn., 2004

Active and Concurrent Topology Maintenance.
Proceedings of the Distributed Computing, 18th International Conference, 2004

Brief announcement: concurrent maintenance of rings.
Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, 2004

The Online Median Problem.
SIAM J. Comput., 2003

On name resolution in peer-to-peer networks.
Proceedings of the 2002 Workshop on Principles of Mobile Computing, 2002

Thread Scheduling for Multiprogrammed Multiprocessors.
Theory Comput. Syst., 2001

Placement Algorithms for Hierarchical Cooperative Caching.
J. Algorithms, 2001

A Superlogarithmic Lower Bound for Shuffle-Unshuffle Sorting Networks.
Theory Comput. Syst., 2000

Analysis of a Local Search Heuristic for Facility Location Problems.
J. Algorithms, 2000

Sorting-Based Selection Algorithms for Hypercubic Networks.
Algorithmica, 2000

Rapid Convergence of a Local Load Balancing Algorithm for Asynchronous Rings.
Theor. Comput. Sci., 1999

Tight Analyses of Two Local Load Balancing Algorithms.
SIAM J. Comput., 1999

Accessing Nearby Copies of Replicated Objects in a Distributed Environment.
Theory Comput. Syst., 1999

Hypercubic Sorting Networks.
SIAM J. Comput., 1998

Sorting Algorithms.
Theory Comput. Syst., 1998

On Contention Resolution Protocols and Associated Probabilistic Phenomena.
J. ACM, 1998

Breaking the Theta (n log² n) Barrier for Sorting with Faults.
J. Comput. Syst. Sci., 1997

Lower Bounds for Shellsort.
J. Algorithms, 1997

Fair On-Line Scheduling of a Dynamic Set of Tasks on a Single Resource.
Inf. Process. Lett., 1997

All Nearest Smaller Values on the Hypercube.
IEEE Trans. Parallel Distributed Syst., 1996

A Comparison of Sorting Algorithms for the Connection Machine CM-2.
Commun. ACM, 1996

Proportionate Progress: A Notion of Fairness in Resource Allocation.
Algorithmica, 1996

A proportional share resource allocation algorithm for real-time, time-shared systems.
Proceedings of the 17th IEEE Real-Time Systems Symposium (RTSS '96), 1996

Fast Fault-Tolerant Concurrent Access to Shared Objects.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

Lower bounds for sorting networks.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Fast scheduling of periodic tasks on multiple resources.
Proceedings of IPPS '95, 1995

Tight Bounds for a Distributed Selection Game with Applications to Fixed-Connection Machines.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

A Lower Bound for Sorting Networks Based on the Shuffle Permutation.
Math. Syst. Theory, 1994

An optimal hypercube algorithm for the all nearest smaller values problem.
Proceedings of the Sixth IEEE Symposium on Parallel and Distributed Processing, 1994

Optimal Parallel Sorting in Multi-Level Storage.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

A Super-Logarithmic Lower Bound for Hypercubic Sorting Networks.
Proceedings of the Automata, Languages and Programming, 21st International Colloquium, 1994

Pipelined Parallel Prefix Computations, and Sorting on a Pipelined Hypercube.
J. Parallel Distributed Comput., 1993

Deterministic Sorting in Nearly Logarithmic Time on the Hypercube and Related Computers.
J. Comput. Syst. Sci., 1993

Sorting-Based Selection Algorithms for Hypercube Networks.
Proceedings of the Seventh International Parallel Processing Symposium, 1993

On the spanning trees of weighted graphs.
Comb., 1992

A Hypercubic Sorting Network with Nearly Logarithmic Depth
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Small-Depth Counting Networks
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Improved Lower Bounds for Shellsort
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

Highly Fault-Tolerant Sorting Circuits
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

A (fairly) Simple Circuit that (usually) Sorts
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Efficient computation on sparse interconnection networks.
PhD thesis, 1989

Load Balancing, Selection Sorting on the Hypercube.
Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, 1989

On the Network Complexity of Selection
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989