Neal E. Young

  Professor Emeritus
Department of Computer Science
University of California
Riverside, CA 92521
www.cs.ucr.edu/~neal
linkedin.com/in/nealeyoung
scholar.google.com/ nealeyoung
 (h-index: 40, citations: 6172 as of January 2023)

Research Interests

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

Education

1991

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

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

1986

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

Experience

1/2020-present

Professor Emeritus, University of California Riverside

8/2016-present

Visiting/Teaching Professor, Computer Science, Northeastern University

4/2010-12/2019

Professor, Computer Science, University of California Riverside

1/2004-3/2010

Associate Professor, Computer Science, University of California Riverside

9/1999-12/2004

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.

9/1995-9/1999

Assistant Professor, Computer Science, Dartmouth

9/1994-9/1995

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

1/1994-8/1994

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

9/1993-1/1997

Consultant, Astrophysics Department, Princeton and Fermilabs, Chicago

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

9/1993-1/1994

Instructor, Computer Science, Princeton

9/1991-8/1993

Postdoc, UMIACS, University of Maryland

12/1991-1/1992

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

graduate school, summer 1988

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

college, summers 1985-1987

Instructor, Center for Talented Youth, Johns Hopkins

college, summers 1984-1985

Programmer, Robotics Project, Computer Science, Cornell University

college, 1/1983-8/1983

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

high school, 9/1981-9/1982

Programmer, Wintek Corporation, Lafayette, Indiana

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

Journal Editor

3/2018-present

Associate Editor, ACM Transactions on Algorithms (TALG)

Graduate Students (sole advisor)

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

2013

Monik Khare*, PhD

2012

Arman Yousefi*, MS

2009

Christos Koufogiannakis*, MS, PhD

2009

Steve Cole*, MS

University Service

2015-2016

UCR CS Department graduate advisor

2014-2016

UCR Campus educational policy committee

2011-2014

UCR Engineering college executive committee

2006-2012, 2014-2015

UCR CS Department undergraduate advisor and chair of undergraduate committee

2010-2012

UCR Campus academic integrity committee

2005-2007

UCR Campus committee on courses

 

Refereeing

National Science Foundation panels (CISE)

Journals. J. ACM, ACM J. Experimental Algorithmics, ACM/IEEE 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, ACM 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), International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), Latin American Theoretical Informatics Symposium (LATIN), Scandinavian Workshop on Algorithm Theory (SWAT).

 

All Publications

2023

Classification via two-way comparisons (extended abstract)

Workshop on Algorithms and Data Structure (WADS)
with Marek Chrobak
Published in Lecture Notes in Computer Science (LNCS Volume 14079, July 2023).

2023

Online paging with heterogeneous cache slots

International Symposium on Theoretical Aspects of Computer Science (STACS)
with Marek Chrobak, Samuel Haney, Mehraneh Liaee, Debmalya Panigrahi, Rajmohan Rajaraman and Ravi Sundaram

2022

A simple algorithm for optimal search trees with 2-way comparisons

ACM Transactions on Algorithms 18(1):1-11(2022)
with Marek Chrobak, Mordecai Golin and J. Ian Munro
See also [Chrobak21Cost, Chrobak22Huang, Chrobak15Optimal.]

2022

On Huang and Wong's algorithm for generalized binary split trees

Acta Informatica:21 pages(2022)
with Marek Chrobak, Mordecai Golin and J. Ian Munro
See also [Chrobak21Cost, Chrobak22Simple, Chrobak15Optimal.]

2021

Comparison and evaluation of state-of-the-art LSM merge policies

The VLDB Journal 30:361-378(2021)
with Qizhong Mao, Steven Jacobs, Waleed Amjad, Vagelis Hristidis and Vassilis Tsotras
Journal version of Mao19Experimental.

2021

Competitive data-structure dynamization

ACM-SIAM Symposium on Discrete Algorithms
with Claire Mathieu, Rajmohan Rajaraman and Arman Yousefi*

2021

On the cost of unsuccessful searches in search trees with two-way comparisons

Information and Computation 218:11 pages(2021)
with Marek Chrobak, Mordecai Golin and J. Ian Munro
See also [Chrobak22Simple, Chrobak22Huang, Chrobak15Optimal]

2019

Experimental evaluation of bounded-depth LSM merge policies

IEEE International Conference on Big Data
with Qizhong Mao, Steven Jacobs, Waleed Amjad, Vagelis Hristidis and Vassilis Tsotras
Conference version of Mao21Comparison.

2019

Unsupervised ontology- and sentiment-aware review summarization

International Conference on Web Information Systems Engineering
with Nhat X.T. Le and Vagelis Hristidis

2018

Balanced centroidal power diagrams for redistricting

ACM International Conference on Advances in Geographic Information Systems
with Vincent Cohen-Addad and Philip Klein

2018

Exploiting transitivity for learning person re-identification models on a budget

IEEE Conference on Computer Vision and Pattern Recognition
with Sourya Roy, Sujoy Paul and Amit K Roy-Chowdhury

2018

Greedy methods (CRC Handbook Chapter 4)

CRC Handbook of Approximation Algorithms and Metaheuristics (Chapter 4)(2018)
with Samir Khuller and Balaji Raghavachari

2017

Ontology- and sentiment-aware review summarization

IEEE International Conference on Data Engineering
with Nhat X.T. Le and Vagelis Hristidis
Poster.

2016

Accelerating the discovery of unsupervised-shapelets

Data Mining and Knowledge Discovery 30(1):243-281(2016)
with Jesin Zakaria, Abdullah Mueen and Eamonn Keogh

2016

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

Springer Encyclopedia of Algorithms:886-889(2016)

2016

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

working paper(2016)

2016

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

Springer Encyclopedia of Algorithms:1457-1461(2016)

2015

Approximation algorithms for the joint replenishment problem with deadlines

Journal of Scheduling 18(6):545-560(2015); (ICALP '13);
with Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Neil Dobbs, Thomas Nowicki, Maxim Sviridenko and Grzegorz Swirszcz
Journal version of [2013].

2015

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)
with Philip Klein
Journal version of [1999]. Published online Aug. 2015.

2015

Optimal search trees with 2-way comparisons

International Symposium on Algorithms and Computation (LNCS 9472)
with Marek Chrobak, Mordecai Golin and J. Ian Munro
Conference version of [Chrobak22Simple, Chrobak21Cost, Chrobak22Huang]

2015

Set-cover approximation (Chapter 40)

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

2014

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

Algorithmica 70(4):648-674(2014); FOCS'07
with Christos Koufogiannakis*
Journal version of [2007].

2014

First-Come-First-Served for online slot allocation and Huffman coding

ACM-SIAM Symposium on Discrete Algorithms
with Monik Khare* and Claire Mathieu

2014

On a linear program for minimum-weight triangulation

SIAM Journal on Computing 43(1):25-51(2014); SODA'12
with Arman Yousefi*
Journal version of [2012].

2013

Approximation algorithms for the joint replenishment problem with deadlines

Automata, Languages, and Programming (ICALP '13); Lecture Notes in Computer Science Volume 7965
with Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Neil Dobbs, Thomas Nowicki, Maxim Sviridenko and Grzegorz Swirszcz
Conference version of [2014].

2013

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

Algorithmica 66(1):113-152(2013); ICALP'09
with Christos Koufogiannakis*
Journal version of [2009].

2013

Hamming approximation of NP witnesses

Theory of Computing 9(22):685-702(2013)
with Daniel Sheldon
First draft circulated in 2003.

2012

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

SIAM Journal on Computing 41(3):684-713(2012); STOC'02
with Mordecai Golin and Claire Mathieu
Journal version of [2002].

2012

On a linear program for minimum-weight triangulation

ACM-SIAM Symposium on Discrete Algorithms
with Arman Yousefi*
Conference version of [2013].

2011

Distributed algorithms for covering, packing and maximum weighted matching

Distributed Computing 24(1):45-63(2011); PODC'09, DISC'09
with Christos Koufogiannakis*
Journal version of two conference papers, on [covering] and [packing].

2011

Logical-shapelets: an expressive primitive for time series classification

ACM International Conference on Knowledge Discovery and Data Mining
with Abdullah Mueen and Eamonn Keogh

2010

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

Algorithms and Theory of Computation Handbook, Second Edition, Volume 1: General Concepts and Techniques(2010)
with Philip Klein

2009

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

ACM Symposium on Principles of Distributed Computing
with Christos Koufogiannakis*
Conference version of part of Distributed algorithms for covering, packing and maximum weighted matching.

2009

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

International Symposium on Distributed Computing
with Christos Koufogiannakis*
Conference version of part of Distributed Algorithms for Covering, Packing and Maximum Weighted Matching.

2009

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

International Colloquium on Automata, Languages, and Programming (LNCS 5555)
with Christos Koufogiannakis*
Conference version of [2013].

2009

Topology management in directional antenna-equipped ad hoc networks

IEEE Transactions on Mobile Computing 8(5):590-605(2009); SECON'06
with Ece Gelal, Gentian Jakllari and Srikanth Krishnamurthy
Journal version of [2006].

2008

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

Springer Encyclopedia of Algorithms(2008)

2008

Incremental medians via online bidding

Algorithmica 50(4):455-478(2008); Latin American Theoretical Informatics (LATIN'06; LNCS 3887:311-322)
with Marek Chrobak, Claire Mathieu and John Noga
Journal version of [2006].

2008

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

Springer Encyclopedia of Algorithms(2008)

2007

Algorithmic approaches to selecting control clones in DNA array hybridization experiments

Journal of Bioinformatics and Computational Biology 5(4):937-961(2007); Asia-Pacific Bioinformatics Conference
with Qi Fu, Elizabeth Bent, James Borneman and Marek Chrobak
Journal version of [2007].

2007

Algorithmic approaches to selecting control clones in DNA array hybridization experiments

Asia-Pacific Bioinformatics Conference
with Qi Fu, Elizabeth Bent, James Borneman and Marek Chrobak
Conference version of [2007].

2007

Beating Simplex for fractional packing and covering linear programs

IEEE Symposium on Foundations of Computer Science
with Christos Koufogiannakis*
Conference version of [2013].

2007

Efficient and effective explanation of change in hierarchical summaries

ACM International Conference on Knowledge Discovery and Data Mining
with Deepak Agarwal, Dhiman Barman, Dimitrios Gunopulos, Flip Korn and Divesh Srivastava

2007

Greedy methods (CRC Handbook Chapter 4)

CRC Handbook of Approximation Algorithms and Metaheuristics (Chapter 4)(2007)
with Samir Khuller and Balaji Raghavachari

2007

Parsimonious explanations of change in hierarchical data

IEEE International Conference on Database Engineering
with Dhiman Barman, Flip Korn, Divesh Srivastava, Dimitrios Gunopulos and Deepak Agarwal
Poster presentation of [2007].

2006

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
with Ece Gelal, Gentian Jakllari and Srikanth Krishnamurthy

2006

Oblivious medians via online bidding

Latin American Theoretical Informatics (LATIN; LNCS 3887)
with Marek Chrobak, Claire Mathieu and John Noga
Conference version of [2008].

2006

The reverse greedy algorithm for the metric k-median problem

Information Processing Letters 97:68-72(2006); COCOON'05
with Marek Chrobak and Claire Mathieu
Journal version of [2005].

2006

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

IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks
with Ece Gelal, Gentian Jakllari and Srikanth Krishnamurthy
Conference version of [2009].

2005

Approximation algorithms for covering/packing integer programs

Journal of Computer and System Sciences 71(4):495-505(2005); FOCS'01
with Stavros Kolliopoulos
Journal version of Tight approximation results for general covering integer programs.

2005

The reverse greedy algorithm for the metric k-median problem

International Computing and Combinatorics Conference
with Marek Chrobak and Claire Mathieu
Conference version of [2006].

2004

Rounding algorithms for a geometric embedding of minimum multiway cut

Mathematics of Operations Research 29(3):0436-0461(2004); STOC'99
with David Karger, Philip Klein, Cliff Stein and Mikkel Thorup
Journal version of [1999].

2003

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

The Astronomical Journal 125:2276-2286(2003)
with Michael R. Blanton, Huan Lin, Robert Lupton and Miller Maley

2002

Huffman coding with unequal letter costs

ACM Symposium on Theory of Computing
with Mordecai Golin and Claire Mathieu
Conference version of [2012].

2002

On-line file caching

Algorithmica 33(3):371-383(2002); SODA'98
Journal version of [1998].

2002

On-line, end-to-end congestion control

IEEE Symposium on Foundations of Computer Science
with Naveen Garg

2001

Sequential and parallel algorithms for mixed packing and covering

IEEE Symposium on Foundations of Computer Science

2001

Tight approximation results for general covering integer programs

IEEE Symposium on Foundations of Computer Science
with Stavros Kolliopoulos
Conference version of Approximation algorithms for covering/packing integer programs.

2000

K-medians, facility location, and the Chernoff-Wald bound

ACM-SIAM Symposium on Discrete Algorithms

2000

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.

2000

Polynomial-time approximation scheme for data broadcast

ACM Symposium on Theory of Computing
with Claire Mathieu and Nicolas Schabanel

1999

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

Algorithms and Theory of Computation Handbook, First Edition(1999)
with Philip Klein

1999

Improved bicriteria existence theorems for scheduling

ACM-SIAM Symposium on Discrete Algorithms
with Jay Aslam, April Rasala and Cliff Stein

1999

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

Integer Programming and Combinatorial Optimization (LNCS 1610)
with Philip Klein
Conference version of [2015].

1999

Rounding algorithms for a geometric embedding of minimum multiway cut

ACM Symposium on Theory of Computing
with David Karger, Philip Klein, Cliff Stein and Mikkel Thorup
Conference version of [2004].

1998

Bounding the diffuse adversary

ACM-SIAM Symposium on Discrete Algorithms
Conference version of On-line paging against adversarially biased random inputs.

1998

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

Journal of Algorithms 27(2):339-356(1998); SODA'96
with Robert Lupton and Miller Maley
Journal version of [1996].

1998

On-line file caching

ACM-SIAM Symposium on Discrete Algorithms
Conference version of [2002].

1997

A codebook generation algorithm for document image compression

IEEE Data Compression Conference
with Qin Zhang and John Danskin

1997

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

Journal of Algorithms 24(2):310-324(1997)
with Sandor Fekete, Samir Khuller, Monika Klemmstein and Balaji Raghavachari

1997

Orienting graphs to optimize reachability

Information Processing Letters 63(5):229-235(1997)
with S. L. Hakimi and Ed Schmeichel

1996

A new operation on sequences: the Boustrophedon transform

Journal of Combinatorial Theory, Series A a76(1):44-54(1996)
with Jessica Millar and Neil Sloane

1996

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

ACM-SIAM Symposium on Discrete Algorithms
with Robert Lupton and Miller Maley
Conference version of [1998].

1996

Low degree spanning trees of small weight

SIAM Journal on Computing 25(2):355-368(1996); STOC'94
with Samir Khuller and Balaji Raghavachari
Journal version of [1994].

1996

On strongly connected digraphs with bounded cycle length

Discrete Applied Mathematics 69(3):281-289(1996)
with Samir Khuller and Balaji Raghavachari

1996

Performance evaluation of approximate priority queues

Fifth DIMACS Implementation Challenge
with Yossi Matias and S. Cenk Sahinalp

1996

Prefix codes: Equiprobable words, unequal letter costs

SIAM Journal on Computing 25(6):1281-1304(1996); ICALP'94
with Mordecai Golin
Journal version of [1994].

1995

Approximating the minimum equivalent digraph

SIAM Journal on Computing 24(4):859-872(1995); SODA'94
with Samir Khuller and Balaji Raghavachari
Journal version of [1994].

1995

Balancing minimum spanning trees and shortest-path trees

Algorithmica 14(4):305-322(1995); SODA'93
with Samir Khuller and Balaji Raghavachari
Journal version of [1993].

1995

Randomized rounding without solving the linear program

ACM-SIAM Symposium on Discrete Algorithms
Lecture notes on this topic are here.

1994

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

Technical Report, School of ORIE, Cornell University 1103(1994)

1994

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

Journal of Algorithms 17(2):280-289(1994); IPCO'93
with Samir Khuller and Uzi Vishkin
Journal version of [1993].

1994

Approximate data structures with applications

ACM-SIAM Symposium on Discrete Algorithms
with Yossi Matias and Jeff Vitter

1994

Approximating the minimum equivalent digraph

ACM-SIAM Symposium on Discrete Algorithms
with Samir Khuller and Balaji Raghavachari
Conference version of [1995].

1994

Designing multi-commodity flow trees

Information Processing Letters 50(1):49-55(1994); WADS'93
with Samir Khuller and Balaji Raghavachari
Journal version of [1993].

1994

Low degree spanning trees of small weight

ACM Symposium on Theory of Computing
with Samir Khuller and Balaji Raghavachari
Conference version of [1996].

1994

Prefix codes: Equiprobable words, unequal letter costs

International Colloquium on Automata, Languages, and Programming
with Mordecai Golin
Conference version of [Golin96Prefix].

1994

Simple strategies for large zero-sum games with applications to complexity theory

ACM Symposium on Theory of Computing
with Richard Lipton

1994

The k-server dual and loose competitiveness for paging

Algorithmica 11(6):525-541(1994); SODA'91
Journal version of [1991].

1993

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

Integer Programming and Combinatorial Optimization
with Samir Khuller and Uzi Vishkin
Conference version of [1994].

1993

Balancing minimum spanning trees and shortest-path trees

ACM-SIAM Symposium on Discrete Algorithms
with Samir Khuller and Balaji Raghavachari
Conference version of [1995].

1993

Designing multi-commodity flow trees

Workshop on Algorithms and Data Structures
with Samir Khuller and Balaji Raghavachari
Conference version of [1994].

1991

Competitive paging algorithms

Journal of Algorithms 12(4):685-699(1991)
with Amos Fiat, Richard Karp, Michael Luby, Lyle McGeoch and Daniel Sleator

1991

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

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

1991

Faster parametric shortest path and minimum balance algorithms

Networks 21(2):205-221(1991)
with Robert Tarjan and James Orlin

1991

Lecture notes on evasiveness of graph properties

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

1991

On-line caching as cache size varies

ACM-SIAM Symposium on Discrete Algorithms
Conference version of The K-Server Dual and Loose Competitiveness for Paging.