Brian C. Dean

Assistant Professor
Division of Computer Science
School of Computing, Clemson University

Office: McAdams Hall, Room 205
Phone: 864-656-5866
Mail: Brian C. Dean, School of Computing, Box 340974, Clemson SC 29634-0974
Email: bcdean@cs.clemson.edu

Bio: I received my undergraduate and graduate degrees in computer science from MIT. My research interests are quite broad, encompassing most of algorithmic computer science and combinatorial optimization. Particular areas of emphasis include approximation algorithms, graph and network optimization problems, scheduling, randomized algorithms and stochastic optimization, data structures, bioinformatics, and data mining. I am also interested in the development of enhanced multimedia content for computer science education, and in the advancement of computer science education at the high-school level.

My research is currently supported by an NSF CAREER award.

Curriculum vitae

Teaching: I'm currently teaching CpSc 840, a graduate course in algorithms. Next fall, I'll be teaching CpSc 838, a graduate course in advanced data structures. Please feel free to contact me for further information.

LectureScribe: In order to develop more effective multimedia content for my courses and an upcoming book, I've written a program called LectureScribe several years back (available here) that provides an easy means of producing animated "whiteboard lectures". LectureScribe records pen input (say, on a Tablet PC) along with audio and produces highly-compressed Macromedia Flash videos as output.

Computing Contests: I'm the associate director of the USA Computing Olympiad, a program that contributes to computer science education at the high-school level via algorithmic programming competitions and on-line training materials.

My wife, Delphine, is an assistant professor in the Clemson Bioengineering department.

Papers:

1.	Rank-Sensitive Priority Queues with Zachary Jones. To appear in the 2009 Algorithms and Data Structures Symposium (WADS).
2.	An Efficient Algorithm for Batch Stability Testing with John Dabney. To appear in Algorithmica.
3.	The Generalized Stable Allocation Problem with Namrata Swar. Proceedings of the Workshop on Algorithms and Computation (WALCOM), pages 238-249, 2009.
4.	Faster Algorithms for Stable Allocation Problems with Siddharth Munshi. Proceedings of the MATCH-UP (Matching Under Preferences) workshop at ICALP, pages 133-144, 2008.
5.	Approximation Algorithms for k-Hurdle Problems with Adam Griffis and Adam A. Whitley. Proceedings of the 8th Conference on Latin American Informatics (LATIN), pages 449-460, 2008.
6.	Exploring the Duality Between Skip Lists and Binary Search Trees with Zachary Jones. Proceedings of the 45 Annual ACM Southeast Regional Conference (ACMSE), pages 395-399, 2007.
7.	Dynamic Homework Annotation Proceedings of the 1st International Workshop on Pen-Based Learning Technologies (PLT), pages 1-5, 2007.
8.	Weighted Alliances in Graphs with Lindsay Jamieson. Congressus Numerantium 187: 76-82, 2007.
9.	Matchability and k-Maximal Matchings with Sandra M. Hedetniemi, Stephen T. Hedetniemi, Jason Lewis, and Alice A. McRae. Submitted to Discrete Applied Mathematics.
10.	A Linear-Time Algorithm for Broadcast Domination in a Tree with John Dabney and Stephen T. Hedetniemi. Networks 53(2), pages 160-169, 2009.
11.	Finite Termination of "Augmenting Path" Algorithms in the Presence of Irrational Problem Data with Michel X. Goemans and Nicole Immorlica. Proceedings of the 14th annual European Symposium on Algorithms (ESA), pages 268-279, 2006.
12.	The Unsplittable Stable Marriage Problem with Michel X. Goemans and Nicole Immorlica. Proceedings of the 4th IFIP International Conference on Theoretical Computer Science, pages 65-75, 2006.
13.	Beyond Screen Capture: Creating Effective Multimedia Whiteboard Lectures on a Tablet PC Proceedings of the 1st Annual Workshop on the Impact of Pen Technology in Education (WIPTE), 2006.
14.	A Simple Expected Running Time Analysis for Randomized "Divide and Conquer" Algorithms Discrete Applied Mathematics 154(1): 1-5. 2006.
15.	Adaptivity and Approximation for Stochastic Packing Problems with Michel X. Goemans and Jan Vondrak. Proceedings of the 16th annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 395-404, 2005.
16.	The Benefit of Adaptivity: Approximating the Stochastic Knapsack Problem with Michel X. Goemans and Jan Vondrak. Mathematics of Operations Research, 33(4), pages 945-964, 2008. Preliminary version appeared in the proceedings of the 45th annual IEEE Symposium on the Foundations of Computer Science (FOCS), pages 208-217, 2004.
17.	Approximation Algorithms for Minimum-Space Advertisement Scheduling with Michel X. Goemans. Submitted to the Journal of Scheduling. Extended abstract appeared in ICALP 2003.
18.	Algorithms for Minimum-Cost Paths in Time-Dependent Networks with Waiting Policies Networks 44(1): 41-46. 2004.
19.	Speeding up Stochastic Dynamic Programming with Zero-Delay Convolution Submitted. Initial version presented at the 2004 MIT student conference of the Lab for Information and Decision Systems (LIDS).
20.	Shortest Paths in FIFO Time-Dependent Networks: Theory and Algorithms Technical report.

Theses:

1.	Approximation Algorithms for Stochastic Scheduling Problems Ph.D. Thesis. 2005.
2.	Continuous-Time Dynamic Shortest Path Algorithms Master's Thesis. 1999.

Copyright Notice. This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

hits according to Web Counter