Publications

• F. Li, C. G. Plaxton, and V. B. Sinha. The obnoxious facility location game with dichotomous preferences. Theoretical Computer Science, 961, 21 pages, 2023. Article 113930.

• F. Li, C. G. Plaxton, and V. B. Sinha. Egalitarian resource sharing over multiple rounds. In Proceedings of the 33rd International Conference on Game Theory, Stony Brook, New York, 25 pages, July 2022.

• C.-K. Lam and C. G. Plaxton. Maximum stable matching with one-sided ties of bounded length. Theory of Computing Systems, 66:645-678, 2022.

• C.-K. Lam and C. G. Plaxton. On the existence of three-dimensional stable matchings with cyclic preferences. Theory of Computing Systems, 66:679-695, 2022.

• F. Li, C. G. Plaxton, and V. B. Sinha. The obnoxious facility location game with dichotomous preferences. In Proceedings of the 22nd Italian Conference on Theoretical Computer Science, Bologna, Italy, pages 219-233, September 2021.

• F. Li, C. G. Plaxton, and V. B. Sinha. The obnoxious facility location game with dichotomous preferences. Technical Report arXiv:2109.05396, 34 pages, September 2021. Revised, May 2023.

• F. Li, C. G. Plaxton, and V. B. Sinha. Egalitarian resource sharing over multiple rounds. Technical Report arXiv:2106.02688, 25 pages, June 2021. Revised, July 2022.

• F. Li, C. G. Plaxton, and V. B. Sinha. Object allocation over a network of objects: Mobile agents with strict preferences (extended abstract). In Proceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems, held online, pages 1578-1580, May 2021.

• F. Li, C. G. Plaxton, and V. B. Sinha. Object allocation over a network of objects: Mobile agents with strict preferences. Technical Report arXiv:2103.01394, 39 pages, March 2021.

• C.-K. Lam and C. G. Plaxton. On the existence of three-dimensional stable matchings with cyclic preferences. In Proceedings of the 12nd International Symposium on Algorithmic Game Theory, Athens, Greece, pages 329-342, October 2019.

• C.-K. Lam and C. G. Plaxton. Maximum stable matching with one-sided ties of bounded length. In Proceedings of the 12nd International Symposium on Algorithmic Game Theory, Athens, Greece, pages 343-356, October 2019.

• C.-K. Lam and C. G. Plaxton. On the existence of three-dimensional stable matchings with cyclic preferences. Technical Report arXiv:1905.02844, 13 pages, May 2019.

• C.-K. Lam and C. G. Plaxton. A (1+1/e)-approximation algorithm for maximum stable matching with one-sided ties and incomplete lists. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, San Diego, California, pages 2823-2840, January 2019.

• C.-K. Lam and C. G. Plaxton. A (ln 4)-approximation algorithm for maximum stable matching with one-sided ties and incomplete lists. Department of Computer Science, University of Texas at Austin, Technical Report TR-18-01, 25 pages, April 2018. See the SODA 2019 version for an improved bound.

• N. O. Domanic, C.-K. Lam, and C. G. Plaxton. Group strategyproof Pareto-stable marriage with indifferences via the generalized assignment game. In Proceedings of the 10th International Symposium on Algorithmic Game Theory, L'Aquila, Italy, pages 280-291, September 2017.

• N. O. Domanic, C.-K. Lam, and C. G. Plaxton. Group strategyproof Pareto-stable marriage with indifferences via the generalized assignment game. Technical Report arXiv:1707.01496, 33 pages, July 2017. Updated version of UTCS TR-17-05.

• N. O. Domanic, C.-K. Lam, and C. G. Plaxton. Group strategyproof Pareto-stable marriage with indifferences via the generalized assignment game. Department of Computer Science, University of Texas at Austin, Technical Report TR-17-05, 33 pages, May 2017.

• N. O. Domanic, C.-K. Lam, and C. G. Plaxton. Strategyproof Pareto-stable mechanisms for two-sided matching with indifferences. In Fourth Workshop on Matching Under Preferences, Cambridge, Massachusetts, 12 pages, April 2017.

• N. O. Domanic, C.-K. Lam, and C. G. Plaxton. Strategyproof Pareto-stable mechanisms for two-sided matching with indifferences. Technical Report arXiv:1703.10598, 28 pages, March 2017. Updated version of UTCS TR-16-19.

• N. O. Domanic, C.-K. Lam, and C. G. Plaxton. Bipartite matching with linear edge weights. In Proceedings of the 27th International Symposium on Algorithms and Computation, Sydney, Australia, pages 28:1-28:13, December 2016.

• N. O. Domanic, C.-K. Lam, and C. G. Plaxton. Strategyproof Pareto-stable mechanisms for two-sided matching with indifferences. Department of Computer Science, University of Texas at Austin, Technical Report TR-16-19, 27 pages, November 2016.

• N. O. Domanic, C.-K. Lam, and C. G. Plaxton. Bipartite matching with linear edge weights. Department of Computer Science, University of Texas at Austin, Technical Report TR-16-15, 38 pages, October 2016.

• N. O. Domanic and C. G. Plaxton. Scheduling unit jobs with a common deadline to minimize the sum of weighted completion times and rejection penalties. In Proceedings of the 25th International Symposium on Algorithms and Computation, Jeonju, Korea, pages 646-657, December 2014.

• N. O. Domanic and C. G. Plaxton. Scheduling unit jobs with a common deadline to minimize the sum of weighted completion times and rejection penalties. Department of Computer Science, University of Texas at Austin, Technical Report TR-14-11, 27 pages, September 2014.

• C. G. Plaxton. Vertex-weighted matching in two-directional orthogonal ray graphs. In Proceedings of the 24th International Symposium on Algorithms and Computation, Hong Kong, pages 524-534, December 2013.

• C. G. Plaxton. Vertex-weighted matching in two-directional orthogonal ray graphs. Department of Computer Science, University of Texas at Austin, Technical Report TR-13-16, 18 pages, September 2013.

• C. G. Plaxton. A simple family of Top Trading Cycles mechanisms for housing markets with indifferences. In Proceedings of the 24th International Conference on Game Theory, Stony Brook, New York, 23 pages, July 2013.

• N. B. Dimitrov and C. G. Plaxton. Optimal cover time for a graph-based coupon collector process. Journal of Discrete Algorithms, 19:39-51, 2013.

• C. G. Plaxton. A simple family of Top Trading Cycles mechanisms for housing markets with indifferences. Department of Computer Science, University of Texas at Austin, Technical Report TR-12-21, 19 pages, October 2012.

• N. B. Dimitrov and C. G. Plaxton. Competitive weighted matching in transversal matroids. Algorithmica, 62:333-348, 2012.

• C. Krishnappa and C. G. Plaxton. A dynamic unit-demand auction supporting bid revision. In Proceedings of the 13rd International Conference on Electronic Commerce, Liverpool, England, 10 pages, August 2011.

• C. Krishnappa and C. G. Plaxton. A sealed-bid unit-demand auction with put options. In Proceedings of the 22nd International Conference on Game Theory, Stony Brook, New York, 50 pages, July 2011.

• C. Krishnappa and C. G. Plaxton. A dynamic unit-demand auction with bid revision and sniping fees. Department of Computer Science, University of Texas at Austin, Technical Report TR-11-30, 12 pages, June 2011.

• C. Krishnappa and C. G. Plaxton. A sealed-bid unit-demand auction with put options. Department of Computer Science, University of Texas at Austin, Technical Report TR-11-04, 50 pages, February 2011.

• N. B. Dimitrov and C. G. Plaxton. Buyer-supplier games: Optimization over the core. Theoretical Computer Science, 412:614-625, 2011.

• C. Krishnappa and C. G. Plaxton. A dynamic unit-demand auction supporting bid revision. Department of Computer Science, University of Texas at Austin, Technical Report TR-10-24, 43 pages, July 2010.

• X. Li, J. Misra, and C. G. Plaxton. Maintaining the Ranch topology. Journal of Parallel and Distributed Computing, 70:1142-1156, 2010.

• N. B. Dimitrov and C. G. Plaxton. Competitive weighted matching in transversal matroids. In Proceedings of the 35th International Colloquium on Automata, Languages, and Programming, Part I, Reykjavik, Iceland, pages 397-408, July 2008.

• C. G. Plaxton. Fast scheduling of weighted tasks with release times and deadlines. In Proceedings of the 35th International Colloquium on Automata, Languages, and Programming, Part I, Reykjavik, Iceland, pages 222-233, July 2008.

• C. G. Plaxton, Y. Sun, M. Tiwari, and H. Vin. Online compression caching. In Proceedings of the 11th Scandinavian Workshop on Algorithm Theory, Gothenburg, Sweden, pages 414-425, July 2008.

• N. B. Dimitrov and C. G. Plaxton. Competitive weighted matching in transversal matroids. Department of Computer Science, University of Texas at Austin, Technical Report TR-08-03, 14 pages, January 2008.

• N. B. Dimitrov and C. G. Plaxton. Buyer-supplier games: Optimization over the core. In Proceedings of the 5th Workshop on Approximation and Online Algorithms, Eilat, Israel, pages 27-40, October 2007.

• C. G. Plaxton, Y. Sun, M. Tiwari, and H. Vin. Reconfigurable resource scheduling with variable delay bounds. In Proceedings of the 21st IEEE International Parallel and Distributed Processing Symposium, Long Beach, California, 10 pages, March 2007.

• C. G. Plaxton, M. Tiwari, and P. Yalagandula. Online aggregation over trees. In Proceedings of the 21st IEEE International Parallel and Distributed Processing Symposium, Long Beach, California, 10 pages, March 2007.

• C. G. Plaxton, Y. Sun, M. Tiwari, and H. Vin. Reconfigurable resource scheduling. In Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures, Cambridge, Massachusetts, pages 93-102, July 2006.

• C. G. Plaxton, Y. Sun, M. Tiwari, and H. Vin. Reconfigurable resource scheduling with variable delay bounds. Department of Computer Science, University of Texas at Austin, Technical Report TR-06-29, 18 pages, July 2006.

• C. G. Plaxton, M. Tiwari, and P. Yalagandula. Online aggregation over trees. Department of Computer Science, University of Texas at Austin, Technical Report TR-06-30, 30 pages, May 2006.

• N. B. Dimitrov and C. G. Plaxton. Buyer-supplier games: Core characterization and computation. Department of Computer Science, University of Texas at Austin, Technical Report TR-06-19, 29 pages, April 2006.

• H. Attiya, F. Kuhn, C. G. Plaxton, M. Wattenhofer, and R. Wattenhofer. Efficient adaptive collect using randomization. Distributed Computing, 18:179-188, 2006.

• X. Li, J. Misra, and C. G. Plaxton. Concurrent maintenance of rings. Distributed Computing, 19:126-148, 2006.

• X. Li, C. G. Plaxton, M. Tiwari, and A. Venkataramani. Online hierarchical cooperative caching. Theory of Computing Systems, 39:851-874, 2006.

• C. G. Plaxton. Approximation algorithms for hierarchical location problems. Journal of Computer and System Sciences, 72:425-443, 2006.

• N. B. Dimitrov and C. G. Plaxton. Optimal cover time for a graph-based coupon collector process. In Proceedings of the 32nd International Colloquium on Automata, Languages, and Programming, Lisboa, Portugal, pages 702-716, July 2005.

• N. B. Dimitrov and C. G. Plaxton. Optimal cover time for a graph-based coupon collector process. Department of Computer Science, University of Texas at Austin, Technical Report TR-05-01, 17 pages, January 2005.

• X. Li, J. Misra, and C. G. Plaxton. Active and concurrent topology maintenance. In Proceedings of the 18th Annual Conference on Distributed Computing, Amsterdam, Netherlands, pages 320-334, October 2004.

• X. Li, J. Misra, and C. G. Plaxton. Brief Announcement: Concurrent maintenance of rings. In Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing, St. John's, Canada, page 376, July 2004.

• X. Li, C. G. Plaxton, M. Tiwari, and A. Venkataramani. Online hierarchical cooperative caching. In Proceedings of the 16th Annual ACM Symposium on Parallelism in Algorithms and Architectures, Barcelona, Spain, pages 74-83, June 2004.

• R. R. Mettu and C. G. Plaxton. Optimal time bounds for approximate clustering. Machine Learning, 56:35-60, 2004.

• C. G. Plaxton. Approximation algorithms for hierarchical location problems. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, San Diego, California, pages 40-49, June 2003.

• R. R. Mettu and C. G. Plaxton. The online median problem. SIAM Journal on Computing, 32:816-832, 2003.

• X. Li and C. G. Plaxton. On name resolution in peer-to-peer networks. Department of Computer Science, University of Texas at Austin, Technical Report TR-02-61, 22 pages, November 2002.

• C. G. Plaxton. Approximation algorithms for hierarchical location problems. Department of Computer Science, University of Texas at Austin, Technical Report TR-02-60, 17 pages, November 2002.

• X. Li and C. G. Plaxton. On name resolution in peer-to-peer networks. In Proceedings of the 2nd Workshop on Principles of Mobile Computing, Toulouse, France, pages 82-89, October 2002.

• R. R. Mettu and C. G. Plaxton. Optimal time bounds for approximate clustering. In Proceedings of the 18th Conference on Uncertainty in Artificial Intelligence, Edmonton, Canada, pages 344-351, August 2002.

• R. R. Mettu and C. G. Plaxton. Optimal time bounds for approximate clustering. Department of Computer Science, University of Texas at Austin, Technical Report TR-01-17, 19 pages, May 2001.

• N. S. Arora, R. D. Blumofe, and C. G. Plaxton. Thread scheduling for multiprogrammed multiprocessors. Theory of Computing Systems, 34:115-144, 2001.

• M. R. Korupolu, C. G. Plaxton, and R. Rajaraman. Placement algorithms for hierarchical cooperative caching. Journal of Algorithms, 38:260-302, 2001.

• R. R. Mettu and C. G. Plaxton. The online median problem. In Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, Redondo Beach, California, pages 339-348, November 2000.

• P. Berthome, A. Ferreira, B. M. Maggs, S. Perennes, and C. G. Plaxton. Sorting-based selection algorithms for hypercubic networks. Algorithmica, 26:237-254, 2000.

• M. R. Korupolu, C. G. Plaxton, and R. Rajaraman. Analysis of a local search heuristic for facility location problems. Journal of Algorithms, 37:146-188, 2000.

• C. G. Plaxton and T. Suel. A super-logarithmic lower bound for shuffle-unshuffle sorting networks. Theory of Computing Systems, 33:233-254, 2000.

• R. R. Mettu and C. G. Plaxton. The online median problem. Department of Computer Science, University of Texas at Austin, Technical Report TR-99-34, 13 pages, November 1999.

• R. D. Blumofe, C. G. Plaxton, and S. Ray. Verification of a concurrent deque implementation. Department of Computer Science, University of Texas at Austin, Technical Report TR-99-11, 20 pages, June 1999.

• M. R. Korupolu, C. G. Plaxton, and R. Rajaraman. Placement algorithms for hierarchical cooperative caching. Department of Computer Science, University of Texas at Austin, Technical Report TR-99-16, 29 pages, June 1999.

• M. R. Korupolu, C. G. Plaxton, and R. Rajaraman. Placement algorithms for hierarchical cooperative caching. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, Maryland, pages 586-595, January 1999.

• J. E. Gehrke, C. G. Plaxton, and R. Rajaraman. Rapid convergence of a local load balancing algorithm for asynchronous rings. Theoretical Computer Science, 220:247-265, 1999.

• B. Ghosh, F. T. Leighton, B. M. Maggs, S. Muthukrishnan, C. G. Plaxton, R. Rajaraman, A. W. Richa, R. E. Tarjan, and D. I. Zuckerman. Tight analyses of two local load balancing algorithms. SIAM Journal on Computing, 29:29-64, 1999.

• C. G. Plaxton, R. Rajaraman, and A. W. Richa. Accessing nearby copies of replicated objects in a distributed environment. Theory of Computing Systems, 32:241-280, 1999.

• N. S. Arora, R. D. Blumofe, and C. G. Plaxton. Thread scheduling for multiprogrammed multiprocessors. In Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures, Puerto Vallarta, Mexico, pages 119-129, June 1998.

• M. R. Korupolu, C. G. Plaxton, and R. Rajaraman. Analysis of a local search heuristic for facility location problems. DIMACS, Technical Report 98-30, 37 pages, June 1998.

• G. E. Blelloch, C. E. Leiserson, B. M. Maggs, C. G. Plaxton, S. J. Smith, and M. Zagha. An experimental analysis of parallel sorting algorithms. Theory of Computing Systems, 31:135-167, March/April 1998.

• P. D. MacKenzie, C. G. Plaxton, and R. Rajaraman. On contention resolution protocols and associated probabilistic phenomena. Journal of the ACM, 45:324-378, March 1998.

• F. T. Leighton and C. G. Plaxton. Hypercubic sorting networks. SIAM Journal on Computing, 27:1-47, February 1998.

• M. R. Korupolu, C. G. Plaxton, and R. Rajaraman. Analysis of a local search heuristic for facility location problems. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, California, pages 1-10, January 1998.

• J. E. Gehrke, C. G. Plaxton, and R. Rajaraman. Rapid convergence of a local load balancing algorithm for asynchronous rings. In Proceedings of the 11th International Workshop on Distributed Algorithms, Saarbrucken, Germany, Lecture Notes in Computer Science, no. 1320, M. Mavronicolas and P. Tsigas (Eds.), pages 81-95, September 1997.

• C. G. Plaxton, R. Rajaraman, and A. W. Richa. Accessing nearby copies of replicated objects in a distributed environment. In Proceedings of the 9th Annual ACM Symposium on Parallel Algorithms and Architectures, Newport, Rhode Island, pages 311-320, June 1997.

• F. T. Leighton, Y. Ma, and C. G. Plaxton. Breaking the $\Theta(n\log^2n)$ barrier for sorting with faults. Journal of Computer and System Sciences, 54:265-304, April 1997.

• C. G. Plaxton, R. Rajaraman, and A. W. Richa. Accessing nearby copies of replicated objects in a distributed environment. Department of Computer Science, University of Texas at Austin, Technical Report TR-97-11, 23 pages, April 1997.

• S. K. Baruah, J. E. Gehrke, C. G. Plaxton, I. Stoica, H. Abdel-Wahab, and K. Jeffay. Fair on-line scheduling of a dynamic set of tasks on a single resource. Information Processing Letters, 64:43-51, 1997.

• C. G. Plaxton and T. Suel. Lower bounds for Shellsort. Journal of Algorithms, 23:221-240, 1997.

• C. G. Plaxton and R. Rajaraman. Fast fault-tolerant concurrent access to shared objects. Department of Computer Science, University of Texas at Austin, Technical Report TR-96-21, 31 pages, December 1996.

• I. Stoica, H. Abdel-Wahab, K. Jeffay, S. K. Baruah, J. E. Gehrke, and C. G. Plaxton. A proportional share resource allocation algorithm for real-time, time-shared systems. In Proceedings of the 17th Annual IEEE Real-Time Systems Symposium, Washington, DC, pages 288-299, December 1996.

• C. G. Plaxton and R. Rajaraman. Fast fault-tolerant concurrent access to shared objects. In Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, Burlington, Vermont, pages 570-579, October 1996.

• S. K. Baruah, J. E. Gehrke, and C. G. Plaxton. Fair on-line scheduling of a dynamic set of tasks on a single resource. Department of Computer Science, University of Texas at Austin, Technical Report TR-96-03, 12 pages, February 1996.

• S. K. Baruah, N. K. Cohen, C. G. Plaxton, and D. A. Varvel. Proportionate progress: A notion of fairness in resource allocation. Algorithmica, 15:600-625, 1996.

• D. Kravets and C. G. Plaxton. All nearest smaller values on the hypercube. IEEE Transactions on Parallel and Distributed Systems, 7:456-462, 1996.

• C. G. Plaxton. Tight bounds for a distributed selection game with applications to fixed-connection machines. In Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, Santa Fe, New Mexico, pages 114-122, October 1995.

• B. Ghosh, F. T. Leighton, B. M. Maggs, S. Muthukrishnan, C. G. Plaxton, R. Rajaraman, A. W. Richa, R. E. Tarjan, and D. I. Zuckerman. Tight analyses of two local load balancing algorithms. In Proceedings of the 27th Annual ACM Symposium on Theory of Computing, Las Vegas, Nevada, pages 548-558, May 1995.

• N. Kahale, F. T. Leighton, Y. Ma, C. G. Plaxton, T. Suel, and E. Szemeredi. Lower bounds for sorting networks. In Proceedings of the 27th Annual ACM Symposium on Theory of Computing, Las Vegas, Nevada, pages 437-446, May 1995.

• S. K. Baruah, J. E. Gehrke, and C. G. Plaxton. Fast scheduling of periodic tasks on multiple resources. In Proceedings of the 9th International Parallel Processing Symposium, Santa Barbara, California, pages 280-288, April 1995.

• S. K. Baruah, J. E. Gehrke, and C. G. Plaxton. Fast scheduling of periodic tasks on multiple resources. Department of Computer Science, University of Texas at Austin, Technical Report TR-95-02, 21 pages, February 1995.

• D. Kravets and C. G. Plaxton. An optimal hypercube algorithm for the all nearest smaller values problem. In Proceedings of the 6th IEEE Symposium on Parallel and Distributed Processing, San Antonio, Texas, pages 505-512, October 1994.

• D. Kravets and C. G. Plaxton. An optimal hypercube algorithm for the all nearest smaller values problem. Department of Computer Science, University of Texas at Austin, Technical Report TR-94-25, 17 pages, October 1994.

• C. G. Plaxton and T. Suel. A super-logarithmic lower bound for hypercubic sorting networks. In Proceedings of the 21st International Colloquium on Automata, Languages, and Programming, Jerusalem, Israel, pages 618-629, July 1994.

• F. T. Leighton and C. G. Plaxton. Hypercubic sorting networks. Department of Computer Science, University of Texas at Austin, Technical Report TR-94-18, 52 pages, May 1994.

• P. D. MacKenzie, C. G. Plaxton, and R. Rajaraman. On contention resolution protocols and associated probabilistic phenomena. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, Montreal, Canada, pages 153-162, May 1994.

• P. D. MacKenzie, C. G. Plaxton, and R. Rajaraman. On contention resolution protocols and associated probabilistic phenomena. Department of Computer Science, University of Texas at Austin, Technical Report TR-94-06, 43 pages, April 1994.

• C. G. Plaxton and T. Suel. A super-logarithmic lower bound for hypercubic sorting networks. Department of Computer Science, University of Texas at Austin, Technical Report TR-94-08, 24 pages, April 1994.

• A. Aggarwal and C. G. Plaxton. Optimal parallel sorting in multi-level storage. In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, Arlington, Virginia, pages 659-667, January 1994.

• G. E. Blelloch, C. E. Leiserson, B. M. Maggs, C. G. Plaxton, S. J. Smith, and M. Zagha. A comparison of sorting algorithms for the Connection Machine CM-2. In Tutorial on Interconnection Networks for Multiprocessors and Multicomputers: Theory and Practice, A. M. Varma and C. S. Raghavendra (Eds.), 1994. IEEE Computer Society Press.

• C. G. Plaxton and T. Suel. A lower bound for sorting networks based on the shuffle permutation. Mathematical Systems Theory, 27:491-508, 1994.

• R. E. Cypher and C. G. Plaxton. Deterministic sorting in nearly logarithmic time on the hypercube and related computers. Journal of Computer and System Sciences, 47:501-548, December 1993.

• A. Aggarwal and C. G. Plaxton. Optimal parallel sorting in multi-level storage. Department of Computer Science, University of Texas at Austin, Technical Report TR-93-22, 24 pages, November 1993.

• P. Berthome, A. Ferreira, B. M. Maggs, S. Perennes, and C. G. Plaxton. Sorting-based selection algorithms for hypercubic networks. In Proceedings of the 7th International Parallel Processing Symposium, Newport Beach, California, pages 89-95, April 1993.

• S. K. Baruah, N. K. Cohen, C. G. Plaxton, and D. A. Varvel. Proportionate progress: A notion of fairness in resource allocation. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing, San Diego, California, pages 345-354, 1993.

• E. W. Mayr and C. G. Plaxton. Pipelined parallel prefix computations, and sorting on a pipelined hypercube. Journal of Parallel and Distributed Computing, 17:374-380, 1993.

• C. G. Plaxton, B. Poonen, and T. Suel. Improved lower bounds for Shellsort. In Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, Pittsburgh, Pennsylvania, pages 226-235, October 1992.

• P. Berthome, A. Ferreira, B. M. Maggs, S. Perennes, and C. G. Plaxton. Sorting-based selection algorithms for hypercubic networks. Laboratoire de l'Informatique du Parallelisme, Institut IMAG, Ecole Normale Superieure de Lyon, Technical Report 92-38, 15 pages, July 1992.

• C. G. Plaxton and T. Suel. A lower bound for sorting networks based on the shuffle permutation. In Proceedings of the 4th Annual ACM Symposium on Parallel Algorithms and Architectures, San Diego, California, pages 70-79, June 1992.

• M. R. Klugerman and C. G. Plaxton. Small-depth counting networks. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, Victoria, Canada, pages 417-428, May 1992.

• C. G. Plaxton. A hypercubic sorting network with nearly logarithmic depth. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, Victoria, Canada, pages 405-416, May 1992.

• B. M. Maggs and C. G. Plaxton. Sorting-based selection algorithms for hypercubic networks. Department of Computer Science, University of Texas at Austin, Technical Report TR-92-22, 13 pages, April 1992.

• C. G. Plaxton and T. Suel. A lower bound for sorting networks based on the shuffle permutation. Department of Computer Science, University of Texas at Austin, Technical Report TR-92-07, 17 pages, March 1992.

• E. W. Mayr and C. G. Plaxton. On the spanning trees of weighted graphs. Combinatorica, 12:433-447, 1992.

• F. T. Leighton, Y. Ma, and C. G. Plaxton. Highly fault-tolerant sorting circuits. In Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science, San Juan, Puerto Rico, pages 458-469, October 1991.

• G. E. Blelloch, C. E. Leiserson, B. M. Maggs, C. G. Plaxton, S. J. Smith, and M. Zagha. A comparison of sorting algorithms for the Connection Machine CM-2. In Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, Hilton Head, South Carolina, pages 3-16, July 1991.

• F. T. Leighton and C. G. Plaxton. A (fairly) simple circuit that (usually) sorts. In Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, St. Louis, Missouri, pages 264-274, October 1990.

• R. E. Cypher and C. G. Plaxton. Deterministic sorting in nearly logarithmic time on the hypercube and related computers. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, Baltimore, Maryland, pages 193-203, May 1990.

• R. E. Cypher and C. G. Plaxton. Techniques for shared key sorting. Computer Science Department, IBM Almaden Research Center, Technical Report RJ 7347, 10 pages, March 1990.

• C. G. Plaxton. On the network complexity of selection. In Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, pages 396-401, October 1989.

• C. G. Plaxton. Efficient computation on sparse interconnection networks. Ph.D. Thesis, Department of Computer Science, Stanford University, 120 pages, September 1989.

• C. G. Plaxton. Efficient computation on sparse interconnection networks. Department of Computer Science, Stanford University, Technical Report STAN-CS-89-1283, 120 pages, September 1989.

• C. G. Plaxton. On the network complexity of selection. Department of Computer Science, Stanford University, Technical Report STAN-CS-89-1276, 18 pages, August 1989.

• C. G. Plaxton. Load balancing on the hypercube and shuffle-exchange. Department of Computer Science, Stanford University, Technical Report STAN-CS-89-1281, 20 pages, August 1989.

• C. G. Plaxton. Load balancing, selection, and sorting on the hypercube. In Proceedings of the 1st Annual ACM Symposium on Parallel Algorithms and Architectures, Santa Fe, New Mexico, pages 64-73, June 1989.

• E. W. Mayr and C. G. Plaxton. Pipelined parallel prefix computations, and sorting on a pipelined hypercube. Department of Computer Science, Stanford University, Technical Report STAN-CS-89-1261, 16 pages, May 1989.

• E. W. Mayr and C. G. Plaxton. On the spanning trees of weighted graphs. In Proceedings of the 14th International Workshop on Graph-Theoretic Concepts in Computer Science, Amsterdam, Netherlands, Lecture Notes in Computer Science, no. 344, J. van Leeuwen (Ed.), pages 394-405, June 1988.

• E. W. Mayr and C. G. Plaxton. Network implementations of the DTEP algorithm. Department of Computer Science, Stanford University, Technical Report STAN-CS-87-1157, 22 pages, May 1987.