Brian C. Dean

Associate 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 computer science education, particularly at the high-school level.

I currently direct the Applied Algorithms Group in the School of Computing at Clemson. My research is currently supported by an NSF CAREER award.

Teaching: This spring (2012) I'm teaching CpSc 840, a graduate course in algorithms. I also organize a weekly graduate algorithms seminar, which meets every Friday 3:30-4:30 [further information and list of talks], as well as a seminar on programming and problem solving [further information] and a creative inquiry seminar for development of new instructional materials for the USA Computing Olympiad.

Advising: If you have taken one of my courses and done well, please feel to contact me about research opportunities. However, my research group is currently quite full, so I am generally not actively seeking new research advisees at this time. I do not currently have any funding available for new students.

Computing Contests: I'm the 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.

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.

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

Papers:

1.	Building Cartesian Trees from Free Trees with Raghuveer Mohan. Submitted for Publication.
2.	Adaptive Stable Marriage Algorithms with John Dabney. Proceedings of the 48th Annual ACM Southeast Regional Conference (ACMSE), 2010.
3.	Speeding up Stochastic Dynamic Programming with Zero-Delay Convolution Algorithmic Operations Research 5(2), 2010, 96-104.
4.	A Linear Programming Approach for Automated Localization of Multiple Faults with Brian Malloy, Will Pressly, and Adam Whitley. Proceedings of Automated Software Engineering (ASE), pages 640-644, 2009.
5.	Rank-Sensitive Priority Queues with Zachary Jones. Proceedings of the Algorithms and Data Structures Symposium (WADS), pages 181-192, 2009.
6.	An Efficient Algorithm for Batch Stability Testing with John Dabney. Algorithmica 58(1), 52-58, 2010.
7.	Matchability and k-Maximal Matchings with Sandra M. Hedetniemi, Stephen T. Hedetniemi, Jason Lewis, and Alice A. McRae. Discrete Applied Mathematics 159(1), 15-22, 2011.
8.	The Generalized Stable Allocation Problem with Namrata Swar. Proceedings of the Workshop on Algorithms and Computation (WALCOM), pages 238-249, 2009.
9.	Faster Algorithms for Stable Allocation Problems with Siddharth Munshi. Algorithmica 58(1), 59-81, 2010.
10.	Approximation Algorithms for k-Hurdle Problems with Adam Griffis, Ojas Parekh, and Adam A. Whitley. Algorithmica 59(1), 81-93, 2011.
11.	Exploring the Duality Between Skip Lists and Binary Search Trees with Zachary Jones. Proceedings of the 45th Annual ACM Southeast Regional Conference (ACMSE), pages 395-399, 2007.
12.	Dynamic Homework Annotation Proceedings of the 1st International Workshop on Pen-Based Learning Technologies (PLT), pages 1-5, 2007.
13.	Weighted Alliances in Graphs with Lindsay Jamieson. Congressus Numerantium 187: 76-82, 2007.
14.	A Linear-Time Algorithm for Broadcast Domination in a Tree with John Dabney and Stephen T. Hedetniemi. Networks 53(2), pages 160-169, 2009.
15.	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.
16.	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.
17.	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.
18.	A Simple Expected Running Time Analysis for Randomized "Divide and Conquer" Algorithms Discrete Applied Mathematics 154(1): 1-5. 2006.
19.	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.
20.	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.
21.	Approximation Algorithms for Minimum-Space Advertisement Scheduling with Michel X. Goemans. Submitted to the Journal of Scheduling. Extended abstract appeared in ICALP 2003.
22.	Algorithms for Minimum-Cost Paths in Time-Dependent Networks with Waiting Policies Networks 44(1): 41-46. 2004.
23.	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