Ali Vakilian

Large volumes of available data have led to the emergence of new computational models for data analysis. One such model is captured by the notion of streaming algorithms: given a sequence of N items, the goal is to compute the value of a given function of the input items by a small number of passes and using a sublinear amount of space in N. Streaming algorithms have applications in many areas such as networking and large scale machine learning. Despite a huge amount of work on this area over the last two decades, there are multiple aspects of streaming algorithms that remained poorly understood, such as (a) streaming algorithms for combinatorial optimization problems and (b) incorporating modern machine learning techniques in the design of streaming algorithms.

In the first part of this thesis, we will describe (essentially) optimal streaming algorithms for set cover and maximum coverage, two classic problems in combinatorial optimization. Next, in the second part, we will show how to augment classic streaming algorithms of the frequency estimation and low-rank approximation problems with machine learning oracles in order to improve their space-accuracy tradeoffs. The new algorithms combine the benefits of machine learning with the formal guarantees available through algorithm design theory.

We consider node-weighted network design problems, in particular the survivable network design problem (SNDP) and its prize-collecting version (PC-SNDP). The input consists of a node-weighted undirected graph G = (V;E) and integral connectivity requirements r(st) for each pair of nodes st. The goal is to find a minimum node-weighted subgraph H of G such that, for each pair st, H contains r(st) disjoint paths between s and t. PC-SNDP is a generalization in which the input also includes a penalty π(st) for each pair, and the goal is to find a subgraph H to minimize the sum of the weight of H and the sum of the penalties for all pairs whose connectivity requirements are not fully satisfied by H. We consider three types of connectivity requirements, edge-connectivity (EC), element-connectivity (ELC) and vertex-connectivity (VC). Let k = max_st r(st) be the maximum requirement. There has been no non-trivial approximation for node-weighted PC-SNDP for k > 1 even in edge-connectivity setup. We describe multiroute-flow based relaxations for PC-EC-SNDP and PC-ELC-SNDP and obtain approximation algorithms for PC-SNDP and PC-ELC-SNDP through them. The approximation ratios we obtain for PC-EC-SNDP are similar to those that were previously known for EC-SNDP via combinatorial algorithms. Specifically, for PC-EC-SNDP (and PC-ELC-SNDP) we obtain an O(k log n)-approximation in general graphs and an O(k)-approximation in graphs that exclude a fixed minor. Moreover, based on the approximation algorithm of ELC-SNDP and the reduction method of [Chuzhoy and Khanna, Theory of Computing 2012] we obtain O(k⁴ log² n)-approximation for PC-VC-SNDP which improves to O(k⁴ log n) on instances from a minor-closed families of graphs.

Publications
Ali Vakilian Postdoctoral Researcher, CS Department, University of Wisconsin—Madison Host: Ilias Diakonikolas Ph.D., EECS Department, MIT Advisors: Erik Demaine and Piotr Indyk M.S., CS Department, University of Illinois at Urbana-Champaign (UIUC) Advisor: Chandra Chekuri B.S., CE Department, Sharif University Research Interests Learning-Based/Data Driven Algorithms [New] STOC'20 Workshop on “Algorithms with Predictions”, June 26, 2020. Workshop on “Learning-Based Algorithms” at TTIC, August 2019. Design and Analysis of Algorithms for Massive Data Approximation Algorithms, Combinatorial Optimization, and Graph Algorithms CV [Last update: June 2020] Email: vakilian[at]mit[dot]edu
Publications (click on [+/-] to see a short summary) Massive Data Graph Algorithms Machine Learning Conference and Journal Papers Individual Fairness for k-Clustering MD ML Sepideh Mahabadi, Ali Vakilian. ICML 2020. Improved Local Computation Algorithm for Set Cover via Sparsification MD GA Christoph Grunau, Slobodan Mitrović, Ronitt Rubinfeld, Ali Vakilian. SODA 2020. Learning-Based Low-Rank Approximations MD ML Piotr Indyk, Ali Vakilian, Yang Yuan. NeurIPS 2019. Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class GA Erik Demaine, Timothy Goodrich, Kyle Kloster, Brian Lavallee, Quanquan Liu, Blair Sullivan, Ali Vakilian, Andrew van der Poel. ESA 2019. [+/-] We developed a generic framework to “round” an input graph into a family of graphs with “certain structures” using a small number of “edits”, then solve the problem on the edited structured graph, and finally “lift” the solution back to get a near optimal solution in the original graph. This rounding framework in particular implies algorithms with improved approximation factors for many classical NP-hard problems such as vertex cover, feedback vertex set, independent set, and many variants of dominating set on graphs close to bounded degenerate, bounded treewidth. Sample-Optimal Low-Rank Approximation of Distance Matrices MD ML Piotr Indyk, Ali Vakilian, Tal Wagner, David Woodruff. COLT 2019. Scalable Fair Clustering MD ML Arturs Backurs, Piotr Indyk, Krzysztof Onak, Baruch Schieber, Ali Vakilian, Tal Wagner. ICML 2019. Tight Trade-offs for Maximum k-Coverage Problem in the General Streaming Model MD Piotr Indyk, Ali Vakilian. PODS 2019. [+/-] We provided a tight trade-off between the space complexity and approximation factor of any single-pass streaming algorithm that estimates the maximum coverage size in the general edge-arrival streaming model (i.e. element-set pairs). This work is among a very few known results on design of streaming algorithms for combinatorial optimization tasks that exploit vector sketching techniques (e.g., l_p-norm estimation and heavy hitters) Learning-Based Frequency Estimation Algorithms MD ML [website] [code] [MIT News, Forbes] Chen-Yu Hsu, Piotr Indyk, Dina Katabi, Ali Vakilian. ICLR 2019. [+/-] We augmented the existing algorithms for frequency estimation with a machine learned oracle for the task of finding heavy hitters. Besides the empirical improvement over the existing methods for frequency estimation (such as Count-Min and Count-Sketch), our approach provably provides better guarantees if the input distribution has certain structure. Moreover, in the worst case scenario, our algorithms match the performance of the best known algorithms for frequency estimation. Local Computation Algorithms for Spanners MD GA Merav Parter, Ronitt Rubinfeld, Ali Vakilian, Anak Yodpinyanee. ITCS 2019. [+/-] We designed the first sub-linear time LCAs for several variants of spanners with constant stretch in general graphs. Generally speaking, given an edge (u,v), our algorithm decides whether the edge is in the spanner in o(\|V\|). Furthermore, the partial answers altogether constitute a single valid output. Set Cover in Sub-linear Time MD Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Ali Vakilian, Anak Yodpinyanee. SODA 2018. [+/-] We provided tight sub-linear algorithms for Set Cover in query access model. Our lower bound results follow by designing two distributions of Set Cover instances that are hard to distinguish. Fractional Set Cover in the Streaming Model MD Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Jonathan Ullman, Ali Vakilian, Anak Yodpinyanee. APPROX 2017. [+/-] We presented a constant-pass algorithm for solving fractional set cover near-optimally in sub-linear space. This was the first instance of covering LPs with a constant pass algorithm in the streaming model. Our algorithm finds a (1+ε)-approximate solution employing the multiplicative weight update method. Cost-Effective Conceptual Design Over Taxonomies Ali Vakilian, Yodsawalai Chodpathumwan, Arash Termehchy, Amir Nayyeri. WebDB 2017. Also in VLDB Journal 2018. Towards Tight Bounds for the Streaming Set Cover Problem MD Sariel Har-Peled, Piotr Indyk, Sepideh Mahabadi, Ali Vakilian. PODS 2016. [+/-] We developed improved constant-pass streaming algorithms for Set Cover. The algorithms turned out to be “the optimal” algorithm for Set Cover (and some other related problems) in several massive data models in subsequent work by us and other researchers. On Streaming and Communication Complexity of The Set Cover Problem MD Erik Demaine, Piotr Indyk, Sepideh Mahabadi, Ali Vakilian. DISC 2014. [+/-] We introduced the “low-approximate” streaming Set Cover where the goal is to obtain near log(n)-approximate solution of Set Cover and presented the first constant-pass algorithm with sub-linear space. Which Concepts are Worth Extracting? Arash Termehchy, Ali Vakilian, Yodsawalai Chodpathumwan, Marianne Winslett. SIGMOD 2014. Also in Transactions on Database Systems (TODS) 2015. Improved Approximation Algorithms for Degree-bounded Network Design Problems with Node Connectivity Requirements GA Alina Ene, Ali Vakilian. STOC 2014. [+/-] we presented the first (O(1),O(1))-bicriteria approximations for several variants of degree-bounded Survivable Network Design problems (SNDP) (e.g. VC-SNDP, k-connected subgraph) addressing several important open questions in the area by Fukunaga-Nutov-Ravi and Cheriyan-Vegh. Prize-collecting Survivable Network Design in Node-weighted Graphs GA Chandra Chekuri, Alina Ene, Ali Vakilian. APPROX 2012 . [+/-] We developed the first non-trivial approximation algorithm for the node-weighted prize-collecting Survivable Network Design problem (SNDP): O(k log n)-approximation where k is the maximum connectivity requirement between any pair of vertices. This improves to O(k) on minor-closed families of graphs. One of our contributions was to define a novel LP relaxation for node-weighted SNDP based on multi-route flows. Node-weighted Network Design in Planar and Minor-closed Families of Graphs GA Chandra Chekuri, Alina Ene, Ali Vakilian. ICALP 2012. [+/-] We considered the node-weighted Survivable Network Design problem (SNDP) on minor-closed families of graphs. Our algorithm achieves an O(k)-approximation where k is the maximum connectivity requirement of any pair of vertices, which improves upon the O(k log n)-approximation of the node-weighted SNDP on general graphs. [arXiv version] builds upon the conference version with results on edge-connectivity and extends its result to the setting with element-connectivity requirements. Manuscripts On Learned Sketches for Randomized Numerical Linear Algebra MD ML Simin Liu, Tianrui Liu, Ali Vakilian, Yulin Wan, David P. Woodruff. July 2020. (Learned) Frequency Estimation Algorithms under Zipfian Distribution MD ML Anders Aamand, Piotr Indyk, Ali Vakilian. February 2020. Approximation Algorithms for Nearly H-Minor-Free Graphs GA Erik Demaine, Quanquan Liu, Ali Vakilian. November 2018 . [+/-] In this work, we generalized existing PTASes for bidimensional parameters on H-minor free graphs to graphs that are somewhat near H-minor free. Connected Domatic Packing in Node-capacitated Graphs GA Alina Ene, Nitish Korula, Ali Vakilian. July 2013. [+/-] Besides our results on fractionally packing connected dominating sets, we designed the first constant factor approximation algorithm for minimum connected dominating set on H-minor-free graphs. Theses New Directions in Streaming Algorithms [abstract] Large volumes of available data have led to the emergence of new computational models for data analysis. One such model is captured by the notion of streaming algorithms: given a sequence of N items, the goal is to compute the value of a given function of the input items by a small number of passes and using a sublinear amount of space in N. Streaming algorithms have applications in many areas such as networking and large scale machine learning. Despite a huge amount of work on this area over the last two decades, there are multiple aspects of streaming algorithms that remained poorly understood, such as (a) streaming algorithms for combinatorial optimization problems and (b) incorporating modern machine learning techniques in the design of streaming algorithms. In the first part of this thesis, we will describe (essentially) optimal streaming algorithms for set cover and maximum coverage, two classic problems in combinatorial optimization. Next, in the second part, we will show how to augment classic streaming algorithms of the frequency estimation and low-rank approximation problems with machine learning oracles in order to improve their space-accuracy tradeoffs. The new algorithms combine the benefits of machine learning with the formal guarantees available through algorithm design theory. [DSpace@MIT] Ph.D. thesis, Department of EECS, MIT, 2019. Node-Weighted Prize-Collecting Survivable Network Design Problems [abstract] We consider node-weighted network design problems, in particular the survivable network design problem (SNDP) and its prize-collecting version (PC-SNDP). The input consists of a node-weighted undirected graph G = (V;E) and integral connectivity requirements r(st) for each pair of nodes st. The goal is to find a minimum node-weighted subgraph H of G such that, for each pair st, H contains r(st) disjoint paths between s and t. PC-SNDP is a generalization in which the input also includes a penalty π(st) for each pair, and the goal is to find a subgraph H to minimize the sum of the weight of H and the sum of the penalties for all pairs whose connectivity requirements are not fully satisfied by H. We consider three types of connectivity requirements, edge-connectivity (EC), element-connectivity (ELC) and vertex-connectivity (VC). Let k = max_st r(st) be the maximum requirement. There has been no non-trivial approximation for node-weighted PC-SNDP for k > 1 even in edge-connectivity setup. We describe multiroute-flow based relaxations for PC-EC-SNDP and PC-ELC-SNDP and obtain approximation algorithms for PC-SNDP and PC-ELC-SNDP through them. The approximation ratios we obtain for PC-EC-SNDP are similar to those that were previously known for EC-SNDP via combinatorial algorithms. Specifically, for PC-EC-SNDP (and PC-ELC-SNDP) we obtain an O(k log n)-approximation in general graphs and an O(k)-approximation in graphs that exclude a fixed minor. Moreover, based on the approximation algorithm of ELC-SNDP and the reduction method of [Chuzhoy and Khanna, Theory of Computing 2012] we obtain O(k⁴ log² n)-approximation for PC-VC-SNDP which improves to O(k⁴ log n) on instances from a minor-closed families of graphs. [IDEALS@UIUC] M.S. thesis, Department of Computer Science, UIUC, 2013. Publication Profiles Google Scholar Profile DBLP Profile
Copyright Notice This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.