Neal E. Young

International Computing and Combinatorics Conference (COCOON)

ACM-SIAM Symposium on Discrete Algorithms (SODA)

Foundations of Software Technology and Theoretical Computer Science (FSTTCS)

International Symposium on Experimental Algorithms (SEA)

Theory and Applications of Models of Computation (TAMC)

International Symposium on Algorithms on Computation (ISAAC)

Scandinavian Symposium and Workshops on Algorithm Theory (SWAT)

Integer Programming and Combinatorial Optimization (IPCO)

Workshop on Approximation and Online Algorithms (WAOA)

Foundations of Software Technology and Theoretical Computer Science (FSTTCS)

ACM-SIAM Symposium on Discrete Algorithms (SODA)

Approximation Algorithms for Combinatorial Optimization Problems (APPROX)

Randomization and Computation (RANDOM)

Monik Khare^*, PhD

Arman Yousefi^*, MS

Christos Koufogiannakis^*, MS, PhD

Steve Cole^*, MS

UCR CS Department graduate advisor

UCR Campus educational policy committee

UCR Engineering college executive committee

UCR CS Department undergraduate advisor and chair of undergraduate committee

UCR Campus academic integrity committee

UCR Campus committee on courses

Method for implementing approximate data structures using operations on machine words

United States patent 5,519,840, Bell Laboratories, with Yossi Matias and Jeff Vitter

Competitive data-structure dynamization

ACM Transactions on Algorithms:just accepted(2024)
with Claire Mathieu, Rajmohan Rajaraman and Arman Yousefi^*
Journal version of [2021].

Online paging with heterogeneous cache slots

with Marek Chrobak, Samuel Haney, Mehraneh Liaee, Debmalya Panigrahi, Rajmohan Rajaraman and Ravi Sundaram
Journal version of [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).

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

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.]

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.]

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.

Competitive data-structure dynamization

ACM-SIAM Symposium on Discrete Algorithms
with Claire Mathieu, Rajmohan Rajaraman and Arman Yousefi^*
Conference version of [2024].

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]

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.

Unsupervised ontology- and sentiment-aware review summarization

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

Balanced centroidal power diagrams for redistricting

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

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

Greedy methods (CRC Handbook Chapter 4)

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

Ontology- and sentiment-aware review summarization

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

Accelerating the discovery of unsupervised-shapelets

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

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);
with Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Neil Dobbs, Thomas Nowicki, Maxim Sviridenko and Grzegorz Swirszcz
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)
with Philip Klein
Journal version of [1999]. Published online Aug. 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]

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
with Christos Koufogiannakis^*
Journal version of [2007].

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

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

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].

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].

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].

Hamming approximation of NP witnesses

Theory of Computing 9(22):685-702(2013)
with Daniel Sheldon
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
with Mordecai Golin and Claire Mathieu
Journal version of [2002].

On a linear program for minimum-weight triangulation

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

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].

Logical-shapelets: an expressive primitive for time series classification

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

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

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.

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.

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].

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].

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

Springer Encyclopedia of Algorithms(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].

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

Springer Encyclopedia of Algorithms(2008)

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].

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].

Beating Simplex for fractional packing and covering linear programs

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

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

Greedy methods (CRC Handbook Chapter 4)

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

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].

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

Oblivious medians via online bidding

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

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].

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].

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.

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].

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].

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

Huffman coding with unequal letter costs

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

On-line file caching

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

On-line, end-to-end congestion control

IEEE Symposium on Foundations of Computer Science
with Naveen Garg

Sequential and parallel algorithms for mixed packing and covering

IEEE Symposium on Foundations of Computer Science

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.

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

ACM-SIAM Symposium on Discrete Algorithms

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.

Polynomial-time approximation scheme for data broadcast

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

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

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

Improved bicriteria existence theorems for scheduling

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

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].

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].

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
with Robert Lupton and Miller Maley
Journal version of [1996].

On-line file caching

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

A codebook generation algorithm for document image compression

IEEE Data Compression Conference
with Qin Zhang and John Danskin

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

Orienting graphs to optimize reachability

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

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

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].

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].

On strongly connected digraphs with bounded cycle length

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

Performance evaluation of approximate priority queues

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

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].

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].

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].

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

Technical Report, School of ORIE, Cornell University 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
with Samir Khuller and Uzi Vishkin
Journal version of [1993].

Approximate data structures with applications

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

Approximating the minimum equivalent digraph

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

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].

Low degree spanning trees of small weight

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

Prefix codes: Equiprobable words, unequal letter costs

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

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

ACM Symposium on Theory of Computing
with Richard Lipton

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
with Samir Khuller and Uzi Vishkin
Conference version of [1994].

Balancing minimum spanning trees and shortest-path trees

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

Designing multi-commodity flow trees

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

Competitive paging algorithms

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

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

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

Faster parametric shortest path and minimum balance algorithms

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

Lecture notes on evasiveness of graph properties

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

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.