# Neal E. Young

Professor; 423 Chung Hall
Department of Computer Science University of California Riverside, CA 92521 (951) 827-7146 |
www.cs.ucr.edu/~neal
linkedin.com/in/nealeyoung scholar.google.com/ nealeyoung (h-index: 35, citations: 4348 as of January 2017) |

## Research Interests

Lagrangian-relaxation algorithms for large-scale linear programming. Online algorithms for caching and data management. Approximation algorithms for NP-hard problems.

## Education

#### Ph.D. Computer Science, Princeton. Hertz fellowship. Advisor: Robert Tarjan

Thesis on competitive analysis of cache-replacement policies, via linear-programming duality.

#### B.A. Computer Science and Mathematics, Cornell. Cum laude with distinction, Phi Beta Kappa

## Experience

#### Visiting Professor, Computer Science, Northeastern University

#### Professor, Computer Science, University of California Riverside

#### Associate Professor, Computer Science, University of California Riverside

#### Senior Research Scientist, Senior Network Architect, Consultant, Akamai Technologies

Designed, coded, and helped deploy a Lagrangian-relaxation-based algorithm to dynamically assign end-users to servers, so as to respect capacity constraints, maximize end-user experience, and reduce bandwidth costs by millions of dollars. Invented TCP/IP variant that maximizes network-wide throughput; applied variant to measure regional bandwidth capacity. Designed, coded, and deployed ``region-health monitor'' to passively detect bandwidth capacities by correlating throughput with packet loss over time.

#### Assistant Professor, Computer Science, Dartmouth

#### Postdoc, AT&T Bell Labs (Mathematical Foundations of Computing, David Johnson's department)

#### Postdoc, Operations Research and Industrial Engineering, Cornell (host Eva Tardos)

#### Consultant, Astrophysics Department, Princeton and Fermilabs, Chicago

Designed and coded Lagrangian-relaxation algorithm to reduce data-collection cost of Sloan Digital Sky Survey.

#### Instructor, Computer Science, Princeton

#### Postdoc, UMIACS, University of Maryland

#### Visitor, Indian Institute of Technology, New Delhi, India (host Vijay Vazirani)

#### Research Intern, DEC Systems Research Center, Palo Alto, California

#### Instructor, Center for Talented Youth, Johns Hopkins

#### Programmer, Robotics Project, Computer Science, Cornell University

#### Programmer, Cornell Programming Environment Project, Computer Science, Cornell University

#### Programmer, Wintek Corporation, Lafayette, Indiana

Coded first generation of smARTWORK printed-circuit-board layout software.

## Funding

#### NSF grant 1619463, Increase the Throughput of Non-relational Databases through Theoretical Modeling and Optimization, $500K (PI, with co-PI Hristidis)

#### Google faculty research award: A Study of Online Bigtable Compaction Algorithms, $50K (sole PI)

#### NSF grant 1117954, Nearly Linear-Time Algorithms for Mixed Packing and Covering Linear Programs, $100K (sole PI)

#### NSF grant 0729071, Approximation Algorithms for Combinatorial Optimization, $312K (PI, with co-PI Chrobak)

#### NSF grant 0626912, Physical Layer Dependent Neighbor Discovery and Topology Management in Ad hoc Networks, $388K (co-PI with Faloutsos and PI Krishnamurthy)

#### NSF CAREER grant 9720664, Combinatorial Approximation Algorithms, $155K (sole PI)

## Selected Publications

*(Advisees are marked with *.)*

#### A nearly linear-time PTAS for explicit fractional packing and covering linear programs

Algorithmica 70(4):648-674(2014); FOCS'07

Journal version of [2007].

#### On a linear program for minimum-weight triangulation

SIAM Journal on Computing 43(1):25-51(2014); SODA'12

Journal version of [2012].

#### Data collection for the Sloan Digital Sky Survey: a network-flow heuristic

Journal of Algorithms 27(2):339-356(1998); SODA'96

Journal version of [1996].

#### Randomized rounding without solving the linear program

ACM-SIAM Symposium on Discrete Algorithms

Lecture notes on this topic are here.

## Graduate Students (sole advisor)

*(Also served on 3-4 PhD committees per year.)*

#### Monik Khare^{*}, PhD

#### Arman Yousefi^{*}, MS

#### Christos Koufogiannakis^{*}, MS, PhD

#### Steve Cole^{*}, MS

## University Service

#### Department graduate advisor

#### Campus educational policy committee

#### Engineering college executive committee

#### Department undergraduate advisor and chair of undergraduate committee

#### Campus academic integrity committee

#### Campus committee on courses

## Patent

## Refereeing

National Science Foundation panels
(CISE)

**Journals.**
J. ACM,
ACM J. Experimental Algorithmics,
ACM Transactions on Networking,
Algorithmica,
J. Algorithms,
Artificial Intelligence,
Cambridge Univ. Press,
J. Combinatorial Optimization,
J. Computer System Sciences,
Discrete Applied Mathematics,
Distributed Computing,
IEEE Transactions on Parallel and Distributed Systems (TPDS),
J. Graph Algorithms and Applications,
Information and Computation,
Information Sciences,
Information Processing Letters,
INFORMS J. Computing,
International
Journal of Foundations of Computer Science,
Machine Learning,
Mathematical Programming,
Mathematica Slovaca,
Mathematics of Operations Research,
Networks,
Operations Research,
SIAM J. Computing,
SIAM J. Discrete Mathematics,
SIAM J. Optimization,
Theoretical Computer Science,
Theory of Computing,
Transactions on Algorithms.

**Conferences.**
ACM Symp. on Theory of Computing (STOC),
ACM-SIAM Symp. on Discrete Algorithms (SODA),
ACM Symposium on Parallel Algorithms and Architectures (SPAA),
ACM Symposium on Principles of Distributed Computing (PODC),
European Symposium on Algorithms (ESA),
International Colloq. on Automata, Languages, and Programming (ICALP),
International Symposium on Algorithms and Computation (ISAAC),
IEEE Symp. on Foundations of Computer Science (FOCS),
The International Computing and Combinatorics Conference (COCOON),
International Symposium on Parallel Architectures, Algorithms & Networks (I-SPAN),
The International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX),
Latin American Theoretical Informatics Symposium (LATIN),
Scandinavian Workshop on Algorithm Theory (SWAT).

## All Publications

#### Accelerating the discovery of unsupervised-shapelets

Data Mining and Knowledge Discovery 30(1):243-281(2016)

#### Greedy set-cover algorithms (part 7 of Encyclopedia of Algorithms)

Springer Encyclopedia of Algorithms:886-889(2016)

#### Nearly linear-work algorithms for mixed packing/covering and facility-location linear programs

working paper(2016)

#### Online paging and caching (part 14 of Encyclopedia of Algorithms)

Springer Encyclopedia of Algorithms:1457-1461(2016)

#### Approximation algorithms for the joint replenishment problem with deadlines

Journal of Scheduling 18(6):545-560(2015); (ICALP '13);

Journal version of [2013].

#### On the number of iterations for Dantzig-Wolfe optimization and packing-covering approximation algorithms

SIAM Journal on Computing 44(4):1154-1172(2015); (IPCO'99)

Journal version of [1999]. Published online Aug. 2015.

#### Optimal search trees with 2-way comparisons

International Symposium on Algorithms and Computation (ISAAC; LNCS 9472)

#### Set-cover approximation (Chapter 40)

Handbook of Graph Theory, Combinatorial Optimization, and Algorithms(2015)

#### A nearly linear-time PTAS for explicit fractional packing and covering linear programs

Algorithmica 70(4):648-674(2014); FOCS'07

Journal version of [2007].

#### On a linear program for minimum-weight triangulation

SIAM Journal on Computing 43(1):25-51(2014); SODA'12

Journal version of [2012].

#### Approximation algorithms for the joint replenishment problem with deadlines

Automata, Languages, and Programming (ICALP '13); Lecture Notes in Computer Science Volume 7965

Conference version of [2014].

#### Greedy Δ-approximation algorithm for covering with arbitrary constraints and submodular cost

Algorithmica 66(1):113-152(2013); ICALP'09

Journal version of [2009].

#### Hamming approximation of NP witnesses

Theory of Computing 9(22):685-702(2013)

First draft circulated in 2003.

#### Huffman coding with unequal letter costs: a linear-time approximation scheme

SIAM Journal on Computing 41(3):684-713(2012); STOC'02

Journal version of [2002].

#### On a linear program for minimum-weight triangulation

ACM-SIAM Symposium on Discrete Algorithms

Conference version of [2013].

#### Distributed algorithms for covering, packing and maximum weighted matching

Distributed Computing 24(1):45-63(2011); PODC'09, DISC'09

Journal version of two conference papers, on
[covering]
and
[packing].

#### Logical-shapelets: an expressive primitive for time series classification

ACM SIGKDD: International Conference on Knowledge Discovery and Data Mining

#### Distributed and parallel algorithms for weighted vertex cover and other covering problems

ACM Symposium on Principles of Distributed Computing (PODC'09)

Conference version of part of Distributed algorithms for covering, packing and maximum weighted matching.

#### Distributed fractional packing and maximum weighted b-matching via tail-recursive duality

The 23rd International Symposium on Distributed Computing (DISC'09)

Conference version of part of Distributed Algorithms for Covering, Packing and Maximum Weighted Matching.

#### Greedy Δ-approximation algorithm for covering with arbitrary constraints and submodular cost

International Colloquium on Automata, Languages, and Programming (ICALP'09) (LNCS 5555)

Conference version of [2013].

#### Topology management in directional antenna-equipped ad hoc networks

IEEE Transactions on Mobile Computing 8(5):590-605(2009); SECON'06

Journal version of [2006].

#### Incremental medians via online bidding

Algorithmica 50(4):455-478(2008); Latin American Theoretical Informatics (LATIN'06; LNCS 3887:311-322)

Journal version of [2006].

#### Algorithmic approaches to selecting control clones in DNA array hybridization experiments

Journal of Bioinformatics and Computational Biology 5(4):937-961(2007); APBC: Asia-Pacific Bioinformatics Conference

Journal version of [2007].

#### Algorithmic approaches to selecting control clones in DNA array hybridization experiments

APBC: Asia-Pacific Bioinformatics Conference

Conference version of [2007].

#### Beating Simplex for fractional packing and covering linear programs

IEEE Symposium on Foundations of Computer Science

Conference version of [2013].

#### Efficient and effective explanation of change in hierarchical summaries

ACM SIGKDD: International Conference on Knowledge Discovery and Data Mining

#### Greedy methods (CRC Handbook Chapter 4)

CRC Handbook of Approximation Algorithms and Metaheuristics (Chapter 4)(2007)

#### Parsimonious explanations of change in hierarchical data

Poster in Proceedings of the IEEE International Conference on Database Engineering (ICDE),

Poster presentation of [2007].

#### An integrated scheme for fully-directional neighbor discovery and topology management in mobile ad hoc networks

MASS: IEEE International Conference on Mobile Ad-hoc and Sensor Systems

#### Oblivious medians via online bidding

Latin American Theoretical Informatics (LATIN; LNCS 3887)

Conference version of [2008].

#### The reverse greedy algorithm for the metric k-median problem

Information Processing Letters 97:68-72(2006); COCOON'05

Journal version of [2005].

#### Topology control to simultaneously achieve near-optimal node degree and low path stretch in ad hoc networks

SECON: IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks

Conference version of [2009].

#### Approximation algorithms for covering/packing integer programs

Journal of Computer and System Sciences 71(4):495-505(2005); FOCS'01

Journal version of Tight approximation results for general covering integer programs.

#### The reverse greedy algorithm for the metric k-median problem

The Computing and Combinatorics Conference 2005 (COCOON)

Conference version of [2006].

#### Rounding algorithms for a geometric embedding of minimum multiway cut

Mathematics of Operations Research 29(3):0436-0461(2004); STOC'99

Journal version of [1999].

#### An efficient targeting strategy for multiobject spectrograph surveys: the Sloan Digital Sky Survey "tiling" algorithm

The Astronomical Journal 125:2276-2286(2003)

#### Huffman coding with unequal letter costs

ACM Symposium on Theory of Computing

Conference version of [2012].

#### Tight approximation results for general covering integer programs

IEEE Symposium on Foundations of Computer Science

Conference version of Approximation algorithms for covering/packing integer programs.

#### On-line paging against adversarially biased random inputs

Journal of Algorithms 37(1):218-235(2000); SODA'98

Journal version of Bounding the diffuse adversary.

#### Approximation algorithms for NP-hard optimization problems (CRC Handbook Chapter 34)

Algorithms and Theory of Computation Handbook, 1st Edition(1999)

#### On the number of iterations for Dantzig-Wolfe optimization and packing-covering approximation algorithms

Integer Programming and Combinatorial Optimization (IPCO'99) (LNCS 1610:320-327)

Conference version of [2015].

#### Rounding algorithms for a geometric embedding of minimum multiway cut

ACM Symposium on Theory of Computing

Conference version of [2004].

#### Bounding the diffuse adversary

ACM-SIAM Symposium on Discrete Algorithms

Conference version of On-line paging against adversarially biased random inputs.

#### Data collection for the Sloan Digital Sky Survey: a network-flow heuristic

Journal of Algorithms 27(2):339-356(1998); SODA'96

Journal version of [1996].

#### A network-flow technique for finding low-weight bounded-degree spanning trees

Journal of Algorithms 24(2):310-324(1997)

#### A new operation on sequences: the Boustrophedon transform

J. Combinatorial Theory, Series A 76(1):44-54(1996)

#### Data collection for the Sloan Digital Sky Survey: a network-flow heuristic

ACM-SIAM Symposium on Discrete Algorithms

Conference version of [1998].

#### Low degree spanning trees of small weight

SIAM Journal on Computing 25(2):355-368(1996); STOC'94

Journal version of [1994].

#### On strongly connected digraphs with bounded cycle length

Discrete Applied Mathematics 69(3):281-289(1996)

#### Prefix codes: Equiprobable words, unequal letter costs

SIAM Journal on Computing 25(6):1281-1304(1996); ICALP'94

Journal version of [1994].

#### Approximating the minimum equivalent digraph

SIAM Journal on Computing 24(4):859-872(1995); SODA'94

Journal version of [1994].

#### Balancing minimum spanning trees and shortest-path trees

Algorithmica 14(4):305-322(1995); SODA'93

Journal version of [1993].

#### Randomized rounding without solving the linear program

ACM-SIAM Symposium on Discrete Algorithms

Lecture notes on this topic are here.

#### A bound on the sum of weighted pairwise distances of points constrained to balls

Cornell University School of ORIE Technical Report 1103(1994)

#### A primal-dual parallel approximation technique applied to weighted set and vertex cover

Journal of Algorithms 17(2):280-289(1994); IPCO'93

Journal version of [1993].

#### Approximating the minimum equivalent digraph

ACM-SIAM Symposium on Discrete Algorithms

Conference version of [1995].

#### Designing multi-commodity flow trees

Information Processing Letters 50(1):49-55(1994); WADS'93

Journal version of [1993].

#### Low degree spanning trees of small weight

ACM Symposium on Theory of Computing

Conference version of [1996].

#### Prefix codes: Equiprobable words, unequal letter costs

International Colloquium on Automata, Languages, and Programming

Conference version of [1996].

#### The k-server dual and loose competitiveness for paging

Algorithmica 11(6):525-541(1994); SODA'91

Journal version of [1991].

#### A primal-dual parallel approximation technique applied to weighted set and vertex cover

Integer Programming and Combinatorial Optimization

Conference version of [1994].

#### Balancing minimum spanning trees and shortest-path trees

ACM-SIAM Symposium on Discrete Algorithms

Conference version of [1995].

#### Designing multi-commodity flow trees

Workshop on Algorithms and Data Structures

Conference version of [1994].

#### Competitive paging and dual-guided algorithms for weighted caching and matching (Thesis)

Technical Report, Computer Science Department, Princeton University CS-TR-348-91(1991)

#### Lecture notes on evasiveness of graph properties

Technical Report, Computer Science Department, Princeton University CS-TR-317-91(1991)