Alina Ene

Authors are ordered alphabetically unless otherwise noted. Co-authors that were my student or postdoc at the time are underlined.

Current Students

Recent Manuscripts

  1. Online and Streaming Algorithms for Constrained k-Submodular Maximization
    Fabian Spaeh, Alina Ene, Huy Le Nguyen
    [arXiv]
  2. META-STORM: Generalized Fully-Adaptive Variance Reduced SGD for Unbounded Functions
    Zijian Liu*, Ta Duy Nguyen*, Thien Hang Nguyen*, Alina Ene, Huy Le Nguyen
    [arXiv]

Conference Publications

  1. On the Generalization Error of Stochastic Mirror Descent for Quadratically-Bounded Losses: an Improved Analysis
    Ta Duy Nguyen, Alina Ene, Huy Le Nguyen
    In Proceedings of the 37th Conference on Neural Information Processing Systems (NeurIPS), 2023
    [NeurIPS]
  2. Improved Convergence in High Probability of Clipped Gradient Methods with Heavy Tailed Noise
    Ta Duy Nguyen*, Thien Hang Nguyen*, Alina Ene, Huy Le Nguyen
    In Proceedings of the 37th Conference on Neural Information Processing Systems (NeurIPS), 2023
    Spotlight presentation
    [arXiv][NeurIPS]
  3. Online Ad Allocation with Predictions
    Fabian Spaeh, Alina Ene
    In Proceedings of the 37th Conference on Neural Information Processing Systems (NeurIPS), 2023
    [arXiv][NeurIPS]
  4. High Probability Convergence of Stochastic Gradient Methods
    Zijian Liu*, Ta Duy Nguyen*, Thien Hang Nguyen*, Alina Ene, Huy Le Nguyen
    In Proceedings of the 40th International Conference on Machine Learning (ICML), 2023
    [arXiv][ICML]
  5. On the Convergence of AdaGrad on $\R^{d}$: Beyond Convexity, Non-Asymptotic Rate and Acceleration
    Zijian Liu*, Ta Duy Nguyen*, Alina Ene, Huy Le Nguyen
    In Proceedings of the 11th International Conference on Learning Representations (ICLR), 2023
    [arXiv][ICLR]
  6. Streaming Algorithm for Monotone k-Submodular Maximization with Cardinality Constraints
    Alina Ene, Huy Le Nguyen
    In Proceedings of the 39th International Conference on Machine Learning (ICML), 2022
    Oral Presentation
    [ICML]
  7. Adaptive Accelerated (Extra-)Gradient Methods with Variance Reduction
    Zijian Liu*, Ta Duy Nguyen*, Alina Ene, Huy Le Nguyen
    In Proceedings of the 39th International Conference on Machine Learning (ICML), 2022
    [arXiv] [ICML]
  8. Adaptive and Universal Algorithms for Variational Inequalities with Optimal Convergence
    Alina Ene, Huy Le Nguyen
    In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), 2022
    [arXiv]
  9. An Efficient Framework for Balancing Submodularity and Cost
    (in contribution order) Sofia Maria Nikolakaki, Alina Ene, Evimaria Terzi
    In Proceedings of the 27th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD), 2021
    [arXiv]
  10. Adaptive Gradient Methods for Constrained Convex Optimization and Variational Inequalities
    Alina Ene, Huy Le Nguyen, Adrian Vladu
    In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), 2021
    [arXiv]
  11. Projection-Free Bandit Optimization with Privacy Guarantees
    Alina Ene, Huy Le Nguyen, Adrian Vladu
    In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), 2021
    [arXiv]
  12. Parallel Algorithm for Non-Monotone DR-Submodular Maximization
    Alina Ene, Huy Le Nguyen
    In Proceedings of the 37th International Conference on Machine Learning (ICML), 2020
    [arXiv] [video]
  13. Optimal Streaming Algorithms for Submodular Maximization with Cardinality Constraints
    Naor Alaluf, Alina Ene, Moran Feldman, Huy Le Nguyen, Andrew Suh
    In Proceedings of the 47th International Colloquium on Automata, Languages and Programming (ICALP), 2020
    [arXiv] [video by my student Andrew]
    Note: This paper is a merger of two preprints: arXiv:1906.11237 and arXiv:1911.12959v1
  14. Improved Convergence for l_infinity and l_1 Regression via Iteratively Reweighted Least Squares
    Alina Ene, Adrian Vladu
    In Proceedings of the 36th International Conference on Machine Learning (ICML), 2019
    [arXiv] [video by my postdoc Adrian]
  15. Towards Nearly-linear Time Algorithms for Submodular Maximization with a Matroid Constraint
    Alina Ene, Huy Le Nguyen
    In Proceedings of the 46th International Colloquium on Automata, Languages and Programming (ICALP), 2019
    [arXiv]
  16. A Nearly-linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
    Alina Ene, Huy Le Nguyen
    In Proceedings of the 46th International Colloquium on Automata, Languages and Programming (ICALP), 2019
    [arXiv]
  17. Submodular Maximization with Matroid and Packing Constraints in Parallel
    Alina Ene, Huy Le Nguyen, Adrian Vladu
    In Proceedings of the 51st ACM Symposium on Theory of Computing (STOC), 2019
    [arXiv]
  18. Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
    Alina Ene, Huy Le Nguyen
    In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2019
    [arXiv]
  19. Mining Tours and Paths in Activity Networks
    (in contribution order) Sofia Maria Nikolakaki, Charalampos Mavroforakis, Alina Ene, Evimaria Terzi
    In Proceedings of The Web Conference (WWW), 2018.
    [pdf]
  20. Decomposable Submodular Function Minimization: Discrete and Continuous
    Alina Ene, Huy Le Nguyen, Laszlo Vegh
    In Proceedings of the 30th Advances in Neural Information Processing Systems (NeurIPS), 2017
    Spotlight presentation
    [pdf] [arXiv]
  21. Approximation Algorithms for Stochastic k-TSP
    Alina Ene, Viswanath Nagarajan, Rishi Saket
    In Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2017
    [arXiv]
  22. Constrained Submodular Maximization: Beyond 1/e
    Alina Ene, Huy Le Nguyen
    In Proceedings of the 57th Annual Symposium on Foundations of Computer Science (FOCS), 2016
    [arXiv]
  23. A New Framework for Distributed Submodular Maximization
    Rafael Barbosa, Alina Ene, Huy Le Nguyen, Justin Ward
    In Proceedings of the 57th Annual Symposium on Foundations of Computer Science (FOCS), 2016
    [arXiv]
  24. On Approximating the Maximum Independent Set of Rectangles
    Julia Chuzhoy, Alina Ene
    In Proceedings of the 57th Annual Symposium on Foundations of Computer Science (FOCS), 2016
    [arXiv]
  25. Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs
    Chandra Chekuri, Alina Ene, Marcin Pilipczuk
    In Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP), 2016
    [pdf]
  26. On Routing Disjoint Paths in Bounded Treewidth Graphs
    Alina Ene, Matthias Mnich, Marcin Pilipczuk, Andrej Risteski
    In Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), 2016
    [arXiv]
  27. Routing under Balance
    Alina Ene, Gary Miller, Jakub Pachocki, Aaron Sidford
    In Proceedings of the 48th ACM Symposium on Theory of Computing (STOC), 2016
    [arXiv]
  28. Submodular Unsplittable Flow on Trees
    Anna Adamaszek, Parinya Chalermsook, Alina Ene, Andreas Wiese
    In Proceedings of the 18th Conference on Integer Programming and Combinatorial Optimization (IPCO), 2016
    [pdf]
  29. Online Buy-at-Bulk Network Design Deeparnab Chakrabarty, Alina Ene, Ravishankar Krishnaswamy, Debmalya Panigrahi
    In Proceedings of the 56th Annual Symposium on Foundations of Computer Science (FOCS), 2015
    [arXiv]
  30. Random Coordinate Descent Methods for Minimizing Decomposable Submodular Functions
    Alina Ene, Huy Le Nguyen
    In Proceedings of the 32nd International Conference on Machine Learning (ICML), 2015
    [arXiv]
  31. The Power of Randomization: Distributed Submodular Maximization on Massive Datasets
    Rafael Barbosa, Alina Ene, Huy Le Nguyen, Justin Ward
    In Proceedings of the 32nd International Conference on Machine Learning (ICML), 2015
    [arXiv]
  32. From Graph to Hypergraph Multiway Partition: Is the Single Threshold the Only Route?
    Alina Ene, Huy Le Nguyen
    In Proceedings of the 22nd European Symposium on Algorithms (ESA), 2014
    [pdf]
  33. Hardness of Submodular Cost Allocation: Lattice Matching and a Simplex Coloring Conjecture
    Alina Ene, Jan Vondrák
    In Proceedings of the 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2014
    [pdf]
  34. Improved Approximation Algorithms for Degree-bounded Network Design Problems with Node Connectivity Requirements
    Alina Ene, Ali Vakilian
    In Proceedings of the 46th ACM Symposium on Theory of Computing (STOC), 2014
    [pdf]
  35. The All-or-Nothing Flow Problem in Directed Graphs with Symmetric Demand Pairs
    Chandra Chekuri, Alina Ene
    In Proceedings of the 16th Conference on Integer Programming and Combinatorial Optimization (IPCO) 2014
    [pdf]
  36. Poly-logarithmic Approximation for Maximum Node Disjoint Paths with Constant Congestion
    Chandra Chekuri, Alina Ene
    In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2013
    [pdf]
  37. Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems
    Alina Ene, Jan Vondrák, Yi Wu
    In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2013
    [arXiv]
  38. Prize-collecting Survivable Network Design in Node-weighted Graphs
    Chandra Chekuri, Alina Ene, Ali Vakilian
    In Proceedings of the 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2012
    [pdf]
  39. Node-weighted Network Design in Planar and Minor-closed Families of Graphs
    Chandra Chekuri, Alina Ene, Ali Vakilian
    In Proceedings of the 39th International Colloquium on Automata Languages and Programming (ICALP), 2012
    [pdf]
  40. Approximation Algorithms and Hardness of Integral Concurrent Flow
    Parinya Chalermsook, Julia Chuzhoy, Alina Ene, Shi Li
    In Proceedings of the 44th ACM Symposium on Theory of Computing (STOC), 2012
    [pdf (extended abstract)] [pdf (full version)]
  41. Geometric Packing under Non-uniform Constraints
    Alina Ene, Sariel Har-Peled, Benjamin Raichel
    In Proceedings of the 28th Annual ACM Symposium on Computational Geometry (SoCG), 2012
    [arXiv]
  42. Approximation Algorithms for Submodular Multiway Partition
    Chandra Chekuri, Alina Ene
    In Proceedings of the 52nd Annual Symposium on Foundations of Computer Science (FOCS), 2011
    [pdf] [arXiv]
  43. Fast Clustering using MapReduce
    Alina Ene, Sungjin Im, Benjamin Moseley
    In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD), 2011
    Oral Presentation
    [arXiv]
  44. Submodular Cost Allocation Problem and Applications
    Chandra Chekuri, Alina Ene
    In Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP), 2011
    [arXiv]
  45. Prize-collecting Steiner Problems on Planar Graphs
    Mohammad Hossein Bateni, Chandra Chekuri, Alina Ene, MohammadTaghi Hajiaghayi, Nitish Korula, and Dániel Marx
    In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011
    [pdf]
  46. Unsplittable Flow in Paths and Trees, and Column-Restricted Packing Integer Programs
    Chandra Chekuri, Alina Ene, Nitish Korula
    In Proceedings of the 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2009
    [pdf]
  47. Fast Exact and Heuristic Methods for Role Minimization Problems
    Alina Ene, William Horne, Nikola Milosavljevic, Prasad Rao, Robert Schreiber, Robert Tarjan
    In Proceedings of the 13th ACM Symposium on Access Control Models and Technologies (SACMAT), 2008
    [pdf]

Journal Publications

  1. An Optimal Streaming Algorithm for Submodular Maximization with Cardinality Constraints
    Naor Alaluf, Alina Ene, Moran Feldman, Huy Le Nguyen, Andrew Suh
    Mathematics of Operations Research (MathOR), 2022.
    [MathOR]
  2. Node-Weighted Network Design in Planar and Minor-Closed Families of Graphs
    Chandra Chekuri, Alina Ene, Ali Vakilian
    Transactions on Algorithms (TALG), 2021.
    [arXiv]
  3. Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs
    Chandra Chekuri, Alina Ene, Marcin Pilipczuk
    SIAM Journal on Discrete Mathematics (SIDMA), 2018
  4. Online Buy-at-Bulk Network Design Deeparnab Chakrabarty, Alina Ene, Ravishankar Krishnaswamy, Debmalya Panigrahi
    SIAM Journal on Computing (SICOMP), 2018
  5. Geometric Packing under Non-uniform Constraints
    Alina Ene, Sariel Har-Peled, Benjamin Raichel
    SIAM Journal on Computing (SICOMP), 2017
  6. Submodular Unsplittable Flow on Trees
    Anna Adamaszek, Parinya Chalermsook, Alina Ene, Andreas Wiese
    Mathematical Programming Series B (MAPR), 2017
  7. The All-or-Nothing Flow Problem in Directed Graphs with Symmetric Demand Pairs
    Chandra Chekuri, Alina Ene
    Mathematical Programming Series B (MAPR), 2015

Manuscripts

  1. A Parallel Double Greedy Algorithm for Submodular Maximization
    Alina Ene, Huy Le Nguyen, Adrian Vladu
    Manuscript, 2018
    [arXiv]
  2. A Reduction for Optimizing Lattice Submodular Functions with Diminishing Returns
    Alina Ene, Huy Le Nguyen
    Manuscript, 2016
    [arXiv]
  3. Connected Domatic Packings in Node-capacitated Graphs
    Alina Ene, Nitish Korula, Ali Vakilian
    Manuscript, 2013
    [pdf]
  4. Fast Clustering with Lower Bounds: No Customer too Far, No Shop too Small
    Alina Ene, Sariel Har-Peled, Benjamin Raichel
    Manuscript, 2013
    [arXiv]

Former Students and Postdocs