Alina Raluca Ene


my photo

I am an Assistant Professor in the Computer Science department at the University of Warwick. I am also affiliated with DIMAP.

Previous Affiliations

Postdoc, Center for Computational Intractability, Princeton University. September 2013 - September 2014.

Ph.D. student (advisor: Chandra Chekuri), Algorithms and Theory Group, Computer Science department, University of Illinois at Urbana-Champaign. August 2008 - July 2013.

Undegraduate student (advisor: Robert Tarjan), Princeton University. September 2004 - June 2008. Graduated with a high honors (magna cum laude) B.S.E. degree in Computer Science.

Research Interests

My research interests are broad, and they span theoretical computer science, optimization, and theoretical machine learning. My interests include submodularity, graph algorithms including routing and network design, algorithms for massive data, and applications in machine learning and computer vision.

Contact

The best way to reach me is by email; A.Ene at dcs dot warwick dot ac dot uk, or aene at cs dot princeton dot edu.

Teaching

CS 254: Algorithmic Graph Theory, Term 2, 2015/16. CS 136: Discrete Mathematics and its Applications I, Term 1, 2015/16.
CS 131: Mathematics for Computer Science II, Term 2, 2014/15.

Students

PhD: Rafael da Ponte Barbosa (2014 -- present)
MSc: Joao Marcal Ramos (2015/16), James Soffe (2014/15)
Undergraduate: Rachel Durant (2015/16), Sara Jenkins (2014/15)

Selected Publications (all)

See all publications. See selected publications.

Copyright warning: The copyright of each published paper belongs to the respective publisher. The local copy is only for non-commercial, personal use.

2016

Routing under Balance (with Gary Miller, Jakub Pachocki and Aaron Sidford). In Proceedings of the 48th ACM Symposium on Theory of Computing (STOC), 2016.
[abstract]

We introduce the notion of \emph{balance} for directed graphs: a weighted directed graph is $\alpha$-balanced if for every cut $S \subseteq V$, the total weight of edges going from $S$ to $V\setminus S$ is within factor $\alpha$ of the total weight of edges going from $V\setminus S$ to $S$. Several important families of graphs are nearly balanced, in particular, Eulerian graphs (with $\alpha = 1$) and residual graphs of $(1+\epsilon)$-approximate undirected maximum flows (with $\alpha=\Oh(1/\epsilon)$).

We use the notion of balance to give a more fine-grained understanding of several well-studied routing questions that are considerably harder in directed graphs. We first revisit oblivious routings in directed graphs. Our main algorithmic result is an oblivious routing scheme for \emph{single-source} instances that achieve an $\Oh(\alpha \cdot \log^3 n / \log \log n)$ competitive ratio. In the process, we make several key technical contributions which may be of independent interest. In particular, we give an efficient algorithm for computing \emph{low-radius decompositions} of directed graphs parameterized by balance. We also define and construct \emph{low-stretch arborescences}, a new concept generalizing low-stretch spanning trees to directed graphs.

On the negative side, we present new lower bounds for oblivious routing problems on directed graphs. We show that the competitive ratio of oblivious routing algorithms for directed graphs has to be $\Omega(n)$ in general; this result improves upon the long-standing best known lower bound of $\Omega(\sqrt{n})$ \cite{HajiaghayiKLR07}. We also show that the restriction to single-source instances is necessary by showing an $\Omega(\sqrt{n})$ lower bound for multiple-source oblivious routing in Eulerian graphs.

We also study the maximum flow problem in balanced directed graphs with arbitrary capacities. We develop an efficient algorithm that finds an $(1+\epsilon)$-approximate maximum flows in $\alpha$-balanced graphs in time $\tilde{\Oh}(m \alpha^2 / \epsilon^2)$. We show that, using our approximate maximum flow algorithm, we can efficiently determine whether a given directed graph is $\alpha$-balanced. Additionally, we give applications to directed sparsest cut problems.

Submodular Unsplittable Flow on Trees (with Anna Adamaszek, Parinya Chalermsook and Andreas Wiese). In Proceedings of the 18th Conference on Integer Programming and Combinatorial Optimization (IPCO), 2016.

2015

On Routing Disjoint Paths in Bounded Treewidth Graphs (with Matthias Mnich, Marcin Pilipczuk and Andrej Risteski). Manuscript, 2015.
[arXiv]

A New Framework for Distributed Submodular Maximization (with Rafael Barbosa, Huy Lê Nguyễn and Justin Ward). Manuscript, 2015.
[abstract][arXiv]

A wide variety of problems in machine learning, including exemplar clustering, document summarization, and sensor placement, can be cast as constrained submodular maximization problems. A lot of recent effort has been devoted to developing distributed algorithms for these problems. However, these results suffer from high number of rounds, suboptimal approximation ratios, or both. We develop a framework for bringing existing algorithms in the sequential setting to the distributed setting, achieving near optimal approximation ratios for many settings in only a constant number of MapReduce rounds. Our techniques also give a fast sequential algorithm for non-monotone maximization subject to a matroid constraint.

Online Buy-at-Bulk Network Design (with Deeparnab Chakrabarty, Ravishankar Krishnaswamy and Debmalya Panigrahi). In Proceedings of the 56th Annual Symposium on Foundations of Computer Science (FOCS), 2015.
[abstract] [arXiv]

We present the first non-trivial online algorithms for the non-uniform, multicommodity buy-at-bulk (MC-BB) network design problem in undirected and directed graphs. Our competitive ratios qualitatively match the best known approximation factors for the corresponding offline problems. The main engine for our results is an online reduction theorem of MC-BB problems to their single-sink (SS-BB) counterparts. We use the concept of junction-tree solutions (Chekuri et al., FOCS 2006) that play an important role in solving the offline versions of the problem via a greedy subroutine -- an inherently offline procedure. Our main technical contribution is in designing an online algorithm using only the existence of good junction-trees to reduce an MC-BB instance to multiple SS-BB sub-instances. Along the way, we also give the first non-trivial online node-weighted/directed single-sink buy-at-bulk algorithms. In addition to the new results, our generic reduction also yields new proofs of recent results for the online node-weighted Steiner forest and online group Steiner forest problems.

Random Coordinate Descent Methods for Minimizing Decomposable Submodular Functions (with Huy Lê Nguyễn). In Proceedings of the 32nd International Conference on Machine Learning (ICML), 2015.
[abstract] [arXiv]

Submodular function minimization is a fundamental optimization problem that arises in several applications in machine learning and computer vision. The problem is known to be solvable in polynomial time, but general purpose algorithms have high running times and are unsuitable for large-scale problems. Recent work have used convex optimization techniques to obtain very practical algorithms for minimizing functions that are sums of "simple" functions. In this paper, we use random coordinate descent methods to obtain algorithms with faster linear convergence rates and cheaper iteration costs. Compared to alternating projection methods, our algorithms do not rely on full-dimensional vector operations and they converge in significantly fewer iterations.

The Power of Randomization: Distributed Submodular Maximization on Massive Datasets (with Rafael Barbosa, Huy Lê Nguyễn and Justin Ward). In Proceedings of the 32nd International Conference on Machine Learning (ICML), 2015.
[abstract] [arXiv]

A wide variety of problems in machine learning, including exemplar clustering, document summarization, and sensor placement, can be cast as constrained submodular maximization problems. Unfortunately, the resulting submodular optimization problems are often too large to be solved on a single machine. We develop a simple distributed algorithm that is embarrassingly parallel and it achieves provable, constant factor, worst-case approximation guarantees. In our experiments, we demonstrate its efficiency in large problems with different kinds of constraints with objective values always close to what is achievable in the centralized setting.

2014

From Graph to Hypergraph Multiway Partition: Is the Single Threshold the Only Route? (with Huy Lê Nguyễn). In Proceedings of the 22nd European Symposium on Algorithms (ESA), 2014.
[pdf]

Hardness of Submodular Cost Allocation: Lattice Matching and a Simplex Coloring Conjecture (with Jan Vondrák). In Proceedings of the 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2014.
[pdf]

Improved Approximation Algorithms for Degree-bounded Network Design Problems with Node Connectivity Requirements (with Ali Vakilian). In Proceedings of the 46th ACM Symposium on Theory of Computing (STOC), 2014.
[pdf]

The All-or-Nothing Flow Problem in Directed Graphs with Symmetric Demand Pairs (with Chandra Chekuri). In Mathematical Programming Series B, December, 2014. Preliminary version in IPCO 2014.
[pdf]

2013

Connected Domatic Packings in Node-capacitated Graphs (with Nitish Korula and Ali Vakilian). Manuscript, 2013.
[pdf]

Poly-logarithmic Approximation for Maximum Node Disjoint Paths with Constant Congestion (with Chandra Chekuri). In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2013.
[pdf]

Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems (with Jan Vondrák and Yi Wu). In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2013.
[arXiv]

Fast Clustering with Lower Bounds: No Customer too Far, No Shop too Small (with Sariel Har-Peled and Benjamin Raichel). Manuscript, 2013.
[arXiv]

2012

Approximation Algorithms for Stochastic k-TSP (with Viswanath Nagarajan and Rishi Saket). Manuscript, 2012.
[abstract]

We consider the stochastic k-TSP problem. There is a metric (V, d) with depot r. Each vertex v in V has a stochastic reward R_v in Z_+. The rewards at different vertices are independent. Given a target value k, the goal is to find an adaptive tour from r that collects reward at least k within the minimum expected length. We give an adaptive O(log k)-approximation algorithm, and a non-adaptive O(log^2 k)-approximation algorithm for the problem.

Prize-collecting Survivable Network Design in Node-weighted Graphs (with Chandra Chekuri and Ali Vakilian). In Proceedings of the 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2012.
[pdf]

Node-weighted Network Design in Planar and Minor-closed Families of Graphs (with Chandra Chekuri and Ali Vakilian). In Proceedings of the 39th International Colloquium on Automata Languages and Programming (ICALP), 2012.
[pdf]

Approximation Algorithms and Hardness of Integral Concurrent Flow (with Parinya Chalermsook, Julia Chuzhoy, and Shi Li). In Proceedings of the 44th ACM Symposium on Theory of Computing (STOC), 2012.
[pdf (extended abstract)] [pdf (full version)]

Geometric Packing under Non-uniform Constraints (with Sariel Har-Peled and Benjamin Raichel). In Proceedings of the 28th Annual ACM Symposium on Computational Geometry (SoCG), 2012.
[arXiv]

2011

Approximation Algorithms for Submodular Multiway Partition (with Chandra Chekuri). In Proceedings of the 52nd Annual Symposium on Foundations of Computer Science (FOCS), 2011.
[pdf] [arXiv]

Fast Clustering using MapReduce (with Sungjin Im and Benjamin Moseley). In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD), 2011. Oral Presentation.
[arXiv]

Submodular Cost Allocation Problem and Applications (with Chandra Chekuri). In Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP), 2011.
[arXiv]

Prize-collecting Steiner Problems on Planar Graphs (with Mohammad Hossein Bateni, Chandra Chekuri, MohammadTaghi Hajiaghayi, Nitish Korula, and Dániel Marx). In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011.
[pdf]

2009

Unsplittable Flow in Paths and Trees, and Column-Restricted Packing Integer Programs (with Chandra Chekuri and Nitish Korula). In Proceedings of the 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2009.
[pdf]

2008

Fast Exact and Heuristic Methods for Role Minimization Problems (with 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]

PhD Thesis

Approximation algorithms for submodular optimization and graph problems. Computer Science Department, UIUC. August 2013.
[pdf]

Program Committees

26th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015.

12th Workshop on Approximation and Online Algorithms (WAOA), 2014.

17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2014.