Design and analysis of algorithms, with a particular emphasis on the
development and analysis of approximation algorithms for NP-hard optimization
problems.
Education
BS Computer Science, Penn State University, 1975
BS Mathematics, Penn State University, 1975
SM Electrical Engineering and Computer Science
Massachusetts Institute of Technology, 1977
PhD Computer Science
Massachusetts Institute of Technology, 1980
Thesis Advisor: Ronald L. Rivest
Thesis: Scheduling Task Systems with Resources
Professional Experience
9/94 - Professor, Computer and Information Sciences,
9/10 - 8/15 Chair, Computer and Information Sciences, University of Delaware
University of Delaware
8/03-7/04 Visiting Professor (sabbatical), Computer Science and Engineering,
Arizona State University
9/94-8/99 Chair, Computer and Information Sciences,
University of Delaware
8/97-10/98 Interim Director, Center for Applied Science and Engineering in
Rehabilitation, University of Delaware
9/89-8/94 Associate Professor of Computer and Information
Sciences, University of Delaware
8/88-8/89 Program Director, Computer and Computation Theory
Program, National Science Foundation
9/86-8/89 Associate Professor of Computer Science, University of
Pittsburgh (on leave 8/88 to 8/89)
9/80-8/86 Assistant Professor of Computer Science, University of
Pittsburgh
9/75-5/80 Research Assistant, Department of Electrical Engineering
and Computer Science, M.I.T. (one semester per year)
9/75-5/80 Teaching Assistant, Department of Electrical Engineering
and Computer Science, M.I.T. (one semester per year)
6/78-9/78 Senior Programmer, Weather Services Corporation
6/77-9/77 Systems Programmer, Data Resources, Inc.
6/75-8/75 Assistant Engineering Programmer, Burroughs Corp
6/74-9/74 Junior Programmer, Burroughs Corporation
Professional Affiliations
Member of the Association for Computing Machinery (ACM)
Member of ACM Special Interest Groups SIGACT and SIGMOBILE
Professional Honors
University of Delaware Faculty Excellence in Teaching Award - 1994
NSF Outstanding Performance Award - 1989
Distinguished Visitor - Department of Computer Science, University of Tennessee - 1987
Nominated (by the department) for a Chancellor's Distinguished
Teaching Award University of Pittsburgh - 1987 and 1988
Professional Activities
Lecturer for IBM Short Course on Programming Languages, Toronto, Canada - 1988
Member - NSF - Visiting Team to DIMACS (S&T Center) - 1990
Panelist - NSF - Research Initiation Awards
Panelist - NSF - Visiting Professorships for Women
Member of the Industrial and Professional Advisory Committee for the Department of Computer
Science and Engineering, Penn State University - 1995-2001
Workshop Chair - ACM Computer Science Conference - 1996
Lecturer for UDel Engineering Outreach Program, Short Course on
C++ and Object Oriented Programming - 1996
General Chair - DIAL M for Mobility Workshop - 2000
Area Editor - "Mobile Algorithms and Complexity" of SIGMOBILE's
Mobile Computing and Communications Review (MC2R) - 2002-2005.
Chair of External Review Team for Computer Science at the College of William and Mary - 2009
Steering Committee Member - DIAL M for Mobility Workshop - 2001-present
Area Editor - Ad Hoc Networks (journal) - 2007-present
External Program Review Team for Graduate Programs in Computer Science at the University of New Hampshire, 2013.
Program Committees - recent only
IEEE Infocom 2010, 2011, 2012, 2013
ICC Ad-hoc, Sensor and Mesh Networking Symposium, 2010, 2011, 2012
SENSORNETS - International Conference on Sensor Networks, 2012
ICACCI -- International Conference on Advances in Computing, Communications and Informatics, 2011
IEEE Wireless Communications and Networking Conference, 2011, 2012
IEEE Globecom Symposium on Wireless Ad hoc and Sensor Networks, 2010, 2011, 2012
IEEE Globecom Wireless Network Symposium, 2010
International Wireless Communications and Mobile Computing Conference, 2011, 2012
External Funding
National Science Foundation, $32,259
Complexity and Optimization, 9/81 - 3/84
National Science Foundation, $47,672
Heuristics for NP-Hard Optimization Problems, 10/83 - 4/86
National Science Foundation, $89,112
Incremental Approximations, 9/92 - 9/95
REU Supplement from NSF for $5000, 5/93-4/94
US Army - Federated Research Laboratory Program: ATIRP
Joint with: 9 other CIS and EE faculty
Lockheed-Martin, Bellcore, GTE, Motorola
U. of Maryland, Howard U., CUNY, and MIT
Award portion to UDEL CIS: $1.5 million 1/96-1/01
My project: Scheduling and Routing in Packet Radio Networks
Award portion: $250,000 1/96-4/01
National Science Foundation CISE Research Infrastructure
Grant: co-PI with 4 co-PIs, and 13 participating
CIS and ECE faculty: $633,513, 7/97-6/02.
US Army Research Laboratories, $3.5 million (UD CIS portion)
Collaborative Technology Alliance Program: CTA: 01-10
Co-PI (with 4 others) for UD portion.
U.S. Army Research Office Scientific Services Program
administered by Battelle Memorial Institute, Contract No. W911NF-11-D-0001,
Analysis of Connected Dominating Set Algorithms, $40,000, 6/12-3/13.
National Science Foundation, $416,102
Ken Barner, PI and 4 co-PIs, including me, Award DUE-1241711
Collaborative Project: A Regional Cybersecurity Education Initiative.
PhD Students
S.S. Ravi - 1984 - Heuristics for PLA Folding: An Analytical Approach
(Distinguished Teaching Professor, SUNY Albany)
J.R.S. Blair - 1986 - The Effects of Wire Topology on Channel Routing
(Professor, US Military Academy - West Point)
V. Winters - 1987 - Effective Generation of Effective Minimal Perfect Hash Functions
S. Ramanathan - 1992 - Communication Scheduling in Packet Radio Networks
(Principal Scientist, BBN)
Z. Ivkovich - 1995 - Incremental approximations
(Associate Professor of Finance, Michigan State University )
H. Tadepalli - 1996 - Scheduling DAGs with Communication Constraints
(Principal System Architect, Broadcom)
X. Ma - 2000 - Adaptive Broadcast Scheduling in Multi-hop Packet Radio Networks
(Staff Scientist, Lucent Technologies)
R. Liu - 2004 - Topology Control for Ad hoc Networks
(Sr. Research Statistician Developer, SAS)
L. Zhao - 2007 - Topology Control for Mobile Ad-hoc Networks
(Data Analyst, WorldQuant )
F. Che - 2011 - Topology Control and Relay Node Placement
(Google)
Publications
"On triangulations of a set of points in the plane," Proceedings of the
Eighteenth Annual IEEE Symposium on the Foundations of Computer Science
(FOCS), 1977, 228-240.
"List scheduling bounds for UET systems with resources," Information Processing
Letters, 10 (1980), 28-31.
"Minimizing channel density in standard cell layout," Algorithmica, 2 (1987),
267-282 (with J.R.S. Blair, S. Kapoor, K. Supowit).
"Scheduling with semaphore constraints," Operations Research Letters, 6
(1987), 121-124.
"On locating minimum feedback vertex sets," Journal of Computer and System
Sciences, 37 (1988), 292-311 (with M.L. Soffa and C.-C. Wang).
"The complexity of near-optimal PLA folding," SIAM Journal on Computing,
17 (1988), 696-710 (with S.S. Ravi).
"A fast algorithm for finding interlocking sets," Information Processing
Letters, 32 (1989), 47-50.
"Concurrent Readers and Writers", Proceedings 5th International Workshop
on Distributed Algorithms (WDAG) (1991), LNCS 579, Editors: S. Toueg, P.
Spirakis, and L. Kirousis (with P. Jayanti and A. Sethi), 212-228.
"A fine grained approach to scheduling asynchronous multimprocessors,"
in Proc. 4th
International Conference on Computing and Information, Toronto, May
1992,
139-142 (with B. Malloy and M. L. Soffa).
"Minimizing external wires in generalized single-row routing," IEEE Transactions
on Computers, 41(1992) 771-775 (with J.R.S. Blair).
" On the Complexity of Distance-2
Coloring with Applications to Radio Networks," in Proc. 4th
International Conference on Computing and Information, Toronto, May
1992, 71-74 (with S. Ramanathan)
"On the Complexity of Link Scheduling in
Multi-hop Radio Networks," in Proc. 26th Conference on Information
Sciences and Systems, Princeton University, Mar. 1992, 491-495 (with S. Ramanathan).
PDF
"The impact of wire topology on single-row routing," Journal of Circuits,
Systems and Computers, 2(1992), 101-112 (with J.R.S. Blair).
"Graph theoretic analysis of PLA folding heuristics," Journal of Computer
and Systems Sciences, 46(1993), 326-348 (with S.S. Ravi) .
"Scheduling algorithms for multihop radio networks," IEEE/ACM Transactions
on Networking, 1(1993), 166-177 (with S. Ramanathan). Earlier version:
Proceedings ACM SIGCOMM conference (1992) (with S. Ramanathan), 211-222.
PDF
"Fully dynamic maintenance of vertex cover," Proceedings of 19th International
Workshop on Graph-Theoretic Concepts in Computer Science (WG'93), J. van
Leeuwen, editor, Lecture Notes in Computer Science No. 790, Springer--Verlag
, 99-111, with Z. Ivkovich).
"Efficient Distributed Algorithms for Channel Assignment in Multihop Radio
Networks", Journal of High Speed Networks, 2(1993), 405-423 (with R. Ramanathan).
"Scheduling DAGs for asynchronous multiprocessor execution," IEEE Transactions
on Parallel and Distributed Computing, 5(1994), 498-508 (with B. Malloy
and M.L.Soffa).
"On k-coloring a set of intervals", Discrete Applied Mathematics 59(1995),
225-235 (with M. Carlisle).
"Partially dynamic bin packing can be solved within 1+e in (amortized)
polylogarithmic time", Information Processing Letters 63(1997) (with Z.
Ivkovich), 45-50.
"Experimental results on broadcast scheduling in packet radio networks,"
Proceedings of the 1st ATIRP Annual Conference, 1997 (with X. Ma).
"Fully dynamic algorithms for bin packing: Being mostly myopic helps,"
SIAM Journal on Computing, 28(1998), 574-611 (with Z. Ivkovich). Earlier
version: Proceedings of the 1st European Symposium on Algorithms (ESA),
(T. Lengauer, ed.) Lecture Notes in Computer Science No. 726, Springer--Verlag
(1993), 226-237, (with Z. Ivkovich).
PDF
"An incremental algorithm for broadcast scheduling in packet radio networks,"
Proceedings of MILCOM 98 (1998) (with X. Ma), 5 pages on CD-ROM. A preliminary
version appeared in: "Practical adaptive algorithms for channel assignment
in multihop packet radio networks," Proceedings of 2nd Advanced Telecommunications
Information Distribution Research Program Conference (ATIRP) (1998) (with
X. Ma)), 60-64.
"A distributed protocol for adaptive broadcast scheduling in packet radio
networks," Workshop record of the 2nd International Workshop on Discrete
Algorithms and Methods for Mobile Computing and Communications (DIAL M
for Mobility), 1998 (with X. Ma), 10 pages. A related version appeared
in: "Distributed broadcast scheduling," Proceedings of 3rd Advanced Telecommunications
Information Distribution Research Program Conference (ATIRP) (1999), (with
X. Ma).
PDF
"Throughput/Delay of Broadcast Scheduling in Multihop Packet Radio Networks
," Proceedings of the 4th Advanced Telecommunications Information Distribution
Research Program Conference (ATIRP) (2000), 239-244, (with X. Ma).
"Experimental Evaluation of a Distributed Broadcast Scheduling Protocol
for Multihop Radio Networks ," 5th Advanced Telecommunications Information
Distribution Research Program Conference (ATIRP) (2001), (with X.
Ma).
"Evaluation of a Distributed Broadcast Scheduling Protocol for Multihop
Radio Networks," Proceedings of MILCOM 2001 (with X. Ma).
"A Distributed Protocol For Adaptive Link Scheduling in Ad-hoc Networks,"
Proceedings of the IASTED International Conference on Wireless and Optical
Communications (WOC2001) (2001), 43-48, (with R. Liu).
"Algorithmic aspects of topology control problems for ad hoc networks," Proceedings
of the
Third ACM International Symposium on Mobile Ad Hoc Networking and Computing
(MobiHoc) (2002), 123--134
(with M. Marathe, R. Ramanathan, S.S. Ravi, and R. Liu).
"Analysis of Queuing Delay in Multimedia Gateway Call Routing,"
Proceedings of the Third International Conference on Internet
Computing (IC2002) (2002),193-198 (with Q. Huang).
PDF
"Broadcast scheduling for TDMA in Wireless Multi-Hop Networks,"
Handbook of Wireless Networks and Mobile Computing, Ivan Stojmenovic,
Editor, John Wiley and Sons, Inc. (2002), 347-370
"Performance analysis of cost optimization
algorithms in multimedia gateway call routing,"
International Conference on Design,
Analysis, and Simulation of Distributed Systems (DASD) ( 2003),
147-154 (with Q. Huang).
DOC
"Algorithmic aspects of topology control," Proceedings of CTA
Conference on Communications and Networks (2003), 17-22
(with R. Liu, S.S. Ravi, M. Marathe,
R. Ramanathan).
"Topology control with diameter constaint," Proceedings of CTA
Conference on Communications and Networks (2003), 313-318
(with R. Liu).
"A parameterized cost model to order classes for integration
testing of C++ applications,"
Proceedings of International Symposium on
Software Reliability Engineering (ISSRE'03),
(2003),
353-364.
(with B. Malloy and P. Clarke).
PDF
"Algorithmic aspects of topology control problems for ad-hoc networks,"
ACM Journal on Mobile Networks and
Applications (MONET), 10(1-2) 2005, 19-34
(with R. Liu, S.S. Ravi,
M. Marathe, R. Ramanathan).
PDF
"Topology control problems under symmetric and asymmetric power
thresholds,"
Proc. International Conference on Ad hoc and Wireless
Networks (ADHOC-NOW'03), (LNCS 2865),
187-198.
(with S. Krumke, R. Liu, M. Marathe, R. Ramanathan, S.S. Ravi).
PDF
"Cost constrained fixed job scheduling",
Proceedings of the 8th Italian Conference, ICTCS 2003, Bertinoro,
Italy, October 2003, "Theoretical Computer Science (LNCS 2841)",
111-124 (with Q. Huang).
PDF
"CLTC: A cluster-based topology control framework for ad-hoc
networks," IEEE Trans. on Mobile
Computing, 3(1) 2004, 18-32
(with C.-C. Shen, C. Srisathatpornphat, R. Liu,
Z. Huang, C. Jaikaeo).
PDF
"Approximating the minimum number of maximum power users
in ad hoc networks",
ACM J. on Mobile Networks and Applications (MONET) 11, 2006, 129-142 (earlier
version in Proc. Third ADHOC-NOW, Lecture Notes in CS, Vol. 3158
(Edited by I. Nikolaidis, M. Barbeau and E. Kranakis),
2004, pp. 1--13.)
(with R. Liu and S.S. Ravi).
PDF
"A study of test coverage adequacy in the presence of stubs",
Journal of Object Technology, 4:5 (2005) 117-137 (with B. Malloy).
the paper
"The impact of clustering in distributed topology control",
International Conference on Communications in Computing
2006 (CIC'06),
(with L. Zhao).
PDF
"The implementation of an extensible system for comparison and
visualization of class ordering methodologies,"
Journal of Systems and Software
79:8 (2006), 1092-1109
(with
N. Kraft, B. Malloy, P. Clarke)
PDF
"A Carrier Sense Multiple Access Protocol with
Power Backoff (CSMA/PB)",
Proceedings of the Fifth IFIP Annual Mediterranean Ad Hoc
Networking
Workshop (MedHocNet'06), (2006), 76-83
(with V. Syrotiuk, C. Colbourn, M. Cui).
PDF
"Topology Control for Simple Mobile Networks",
IEEE Globecom 2006 - Wireless Ad Hoc and Sensor Networks Symposium, 2006,
6 pages on CD-ROM (with L. Zhao and S.S. Ravi).
PDF
"Topology Control for Constant Rate Mobile Networks",
IEEE Globecom 2006 - Wireless Communications and Networking Symposium, 2006,
6 pages on CD-ROM (with L. Zhao and S.S. Ravi).
PDF
"Relay Node Placement in Wireless Sensor Networks", IEEE Transactions on Computers
56(2007), 134-138, (with G. Xue).
PDF
"A Carrier Sense Multiple Access Protocol with
Power Backoff (CSMA/PB)",
Journal of Ad Hoc Networks 5(2007), 1233-1250,
(with V. Syrotiuk, C. Colbourn, M. Cui).
PDF
"Fault-tolerant Relay Node Placement in Heterogeneous Wireless Sensor Networks,"
IEEE Infocom 2007,
(with X. Han, X. Cao, E. Lloyd, C-C. Shen).
PDF
"Topology Control Problems for Wireless Ad Hoc Networks,"
Handbook of Approximation Algorithms and Metaheuristics,
Teofilo Gonzalez,
Editor, Chapman and Hall/CRC (2007), 67-1 to 67-20, (with S.S. Ravi)
"Optimal Relay Node
Fault Recovery",
2nd International Workshop on Advances in Wireless Sensor Networks
(IWASN), 2007, 8 pages on CD-ROM (with
F. Che, and L. Zhao).
PDF
"Efficient Probe Selection Algorithms for Fault Diagnosis,"
Telecommunications Systems Journal 37(2008), 109-125 (with M. Natu and A. Sethi).
PDF
"Deploying Directional Sensor Networks with Guaranteed Connectivity and Coverage,"
5th IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks
- SECON 2008, 8 pages on CD (with X. Han, X. Cao and C.-C. Shen).
PDF
"Improved topology control algorithms for Simple Mobile Networks,"
Ad Hoc Nets '09, 10 pages
PDF
(F. Che, E. Lloyd and L. Zhao).
"The Complexity of RP Selection in Multicast
Channelization,"
Milcom '09, 6 pages
PDF
(with F. Che)
"Incremental Channelization,"
Milcom '09, 6 pages
PDF
(with F. Che)
"On-line Bin Packing",
Fundamental Problems in Computing
- Essays in Honor of Professor Daniel J. Rosenkrantz,
S.S. Ravi, S. Shukla, K. Sandeep, eds. (2009), 25 pages
(with Z. Ivkovic)
"Fault-tolerant Relay Node Placement in Heterogeneous Wireless Sensor Networks,"
IEEE Trans. on Mobile Computing, 9(2010), 643 - 656.
(with X. Han, X. Cao and C.-C. Shen).
"Topology Control in Constant Rate Mobile Ad Hoc Networks,"
Wireless Networks, 16(2010), 467 - 480.
(with L. Zhao and S.S. Ravi).
PDF
"Reverse Engineering Interface Protocols
for Comprehension of Large C++ Libraries
during Code Evolution Tasks," Journal of Software Engineering and Knowledge Engineering}, 24 pages (2011),
(with
Edward B. Duffy, Jason O. Hallstrom and Brian A. Malloy).
"Relay Node Placement with Limited Relays," IEEE Globecom 2012, 7 pages (2012)
PDF
(with F. Che, J. Hallstrom, and S.S. Ravi).
"Deploying Directional Sensor Networks with Guaranteed
Connectivity and Coverage," Submitted to a journal
(with X. Han, X. Cao and C.-C. Shen).
"Simulation Analysis of Distributed CDS Algorithms," Submitted to a conference (with Y. Khadke, K. Ma, B. Graff, M. Patel), 2013.