Research

Working Papers

  • On the Burer-Monteiro Optimization for Rank Constrained Semidefinite Programming.
  • Optimal Dispatch of Firefighters from Multiple Stations.

Preprints

  • Hardness and Approximation of Submodular Minimum Linear Ordering Problems.
    With Swati Gupta, Shengding Sun, Prasad Tetali, Michael C. Wigal.
    arXiv

    The minimum linear ordering problem (MLOP) seeks to minimize an aggregated cost f(\cdot) due to an ordering \sigma of the items (say [n]), i.e., \min_{\sigma} \sum_{i\in [n]} f(E_{i,\sigma}), where E_{i,\sigma} is the set of items that are mapped by \sigma to indices at most i. This problem has been studied in the literature for various special cases of the cost function f, and in a general setting for a submodular or supermodular cost f [ITT2012]. Though MLOP was known to be NP-hard for general submodular functions, it was unknown whether the special case of graphic matroid MLOP (with f being the matroid rank function of a graph) was polynomial-time solvable. Following this motivation, we explore related classes of linear ordering problems, including symmetric submodular MLOP, minimum latency vertex cover, and minimum sum vertex cover. We show that the most special cases of our problem, graphic matroid MLOP and minimum latency vertex cover, are both NP-hard.

    We further expand the toolkit for approximating MLOP variants: using the theory of principal partitions, we show a 2-\frac{1+\ell_{f}}{1+|E|} approximation to monotone submodular MLOP, where \ell_{f}=\frac{f(E)}{\max_{x\in E}f(\{x\})} satisfies 1 \leq \ell_f \leq |E|. Thus our result improves upon the best known bound of 2-\frac{2}{1+|E|} by Iwata, Tetali, and Tripathi [ITT2012]. This leads to a 2-\frac{1+r(E)}{1+|E|} approximation for the matroid MLOP, corresponding to the case when r is the rank function of a given matroid. Finally, we show that MLVC can be 4/3 approximated, matching the integrality gap of its vanilla LP relaxation.

  • λ & Maximum Variance Embedding: Measuring and Optimizing Connectivity of A Graph Metric.
    With Anand Louis, Mohit Singh, and Prasad Tetali.
    arXiv

Published

  • J2
    Bridging Classical and Quantum with SDP initialized warm-starts for QAOA.
    To appear in ACM Transactions on Quantum Computing.
    With Reuben Tate, Creston Herold, Greg Mohler, and Swati Gupta.
    arXiv

    We study the Quantum Approximate Optimization Algorithm (QAOA) in the context of the Max-Cut problem. Near-term (noisy) quantum devices are only able to (accurately) execute QAOA at low circuit depths while QAOA requires a relatively high circuit-depth in order to "see" the whole graph. We introduce a classical pre-processing step that initializes QAOA with a biased superposition of all possible cuts in the graph, referred to as a warm-start. In particular, our initialization informs QAOA by a solution to a low-rank semidefinite programming relaxation of the Max-Cut problem. Our experimental results show that this variant of QAOA, called QAOA-Warm, is able to outperform standard QAOA on lower circuit depths with less training time (in the optimization stage for QAOA's variational parameters). We provide experimental evidence as well as theoretical intuition on performance of the proposed framework.

  • C6
    The Traveling Firefighter Problem.
    In ACDA 2021 -- Proceedings of SIAM Conference on Applied and Computational Discrete Algorithms, July 2021.
    With Alejandro Toriello, and Prasad Tetali.
    arXiv slides

    We studied variants of the Traveling Salesman Problem whose objective can be more efficient, fair, and adjustable to various applications, e.g., ride-sharing from costumer vs server perspective, containment of wildfires, etc. In contrast to path-TSP, we generalize the objective to be an arbitrary norm of the delay/service-time vector.

    We developed efficient randomized algorithms with approximate optimality guarantees for such APX-hard problems in general metrics.

    We also provided an approximation preserving reduction from the problem with any Minkowski norm of the delay vector as the (non-linear) objective, to a variant of TSP with a constant number of deadlines.

  • C5
    Improved Approximations for Min Sum Vertex Cover and Generalized Min Sum Set Cover.
    In SODA 2021 -- Proceedings of ACM-SIAM Symposium on Discrete Algorithms, January 2021.
    With Nikhil Bansal, Jatin Batra, and Prasad Tetali.
    arXiv

    In min sum vertex cover (MSVC) the goal is to find an ordering of the vertices of a graph to minimize the average cover time of its edges. An edge is covered when one of its endpoints appears in the ordering. We give a 16/9 = 1.778 approximation for MSVC, and show a matching integrality gap for the natural LP relaxation. This improves upon the previous best 1.999946 approximation of Barenholz, Feige and Peleg.

    We also study a much more general problem known as multiple intents ranking, or generalized min sum set cover (GMSSC), wherein given a hypergraph, each hyperedge is considered covered by the first time when a given number of its vertices appear in the ordering. We give a 4.642 approximation algorithm for GMSSC, coming close to the best possible bound of 4, already for the classical special case of min sum set cover (MSSC) studied by Feige, Lovász and Tetali, and improving upon the previous best known bound of 12.4 due to Im, Sviridenko and van der Zwaan.

    Our algorithm is based on transforming the LP solution by a suitable kernel and applying randomized rounding. This also gives an LP-based 4 approximation for MSSC. As part of the analysis of our algorithm, we also derive an inequality on the lower tail of a sum of independent Bernoulli random variables, which might be of independent interest and broader utility.

  • C4
    Low Complexity Heart Rate Measurement from Wearable Wrist-Type Photoplethysmographic Sensors Robust to Motion Artifacts.
    In ICASSP 2018 -- Proceedings of 43rd IEEE International Conference on Acoustics, Speech and Signal Processing, April 2018.
    With Mahdi B Mashhadi, Mahmoud Essalat, and Farokh Marvasti.
    pdf

    We presented a low complexity while accurate Heart Rate (HR) estimation technique from signals captured by Photoplethysmographic (PPG) sensors worn on the wrist during intensive physical exercise. Wrist-type PPG signals experience severe Motion Artifacts (MA) that hinder efficient HR estimation especially during intensive physical exercises. To suppress the motion artifacts efficiently, simultaneous 3 dimensional acceleration signals are used as reference MAs.

    We introduced heuristics to recover, denoise, and post-process the spectrum of the heart beat signal, to track and predict HR time series.

    The proposed method achieved an Average Absolute Error (AAE) of 1.19 Beats Per Minute (BPM) on the 12 benchmark PPG recordings in which subjects run at speeds of up to 15 km/h. This method also achieves an AAE of 2.17 BPM on the whole benchmark database of 23 recordings that include both running and arm movement activities.

    The proposed method achieved comparable accuracy with state-of-the-art algorithms while at a significantly reduced computational cost which makes its standalone implementation on wearable devices feasible. The proposed algorithm achieves an average processing time of 32 milliseconds per input frames of length 8 seconds (2 channel PPG and 3D ACC signals) on a 3.2 GHz processor.

  • C3
    Routing in Well-Separated Pair Decomposition Spanners.
    In ICCG 2018 -- Proceedings of 1st Iranian Conference on Computational Geometry, February 2018.
    With Fatemeh Baharifard, and Hamid Zarrabi-Zadeh.
    pdf

    We presented a local and arbitrary precise routing scheme for the well-separated pair decomposition (WSPD) spanners, using compressed quadtrees. Given a point set P in the plane, a WSPD spanner is a geometric graph whose vertex set is P, and for each pair (A, B) in the WSPD of P, an edge is added to the graph from an arbitrary point in A to an arbitrary point in B.

  • J1
    Expand the Shares Together: Envy-Free Mechanisms with a Small Number of Cuts.
    In Algorithmica.
    With Masoud Seddighin, Mohammad Ghodsi, Reza Alijani, and Ahmad S Tajik.
    pdf

    We study the problem of fair division of a heterogeneous resource among strategic players. Given a divisible heterogeneous cake, we wish to divide the cake among n players in a way that meets the following criteria: (I) every player(weakly) prefers his allocated cake to any other player’s share (such notion is known as envy-freeness), (II) the mechanism is strategy-proof (truthful), and (III) the number of cuts made on the cake is minimal. We provide methods, namely expansion process and expansion process with unlocking, for dividing the cake under different assumptions on the valuation functions of the players.

  • C2
    Envy-free mechanisms with minimum number of cuts.
    In AAAI 2017 -- Proceedings of 31st AAAI Conference on Artificial Intelligence, February 2017.
    With Reza Alijani, Mohammad Ghodsi, Masoud Seddighin, and Ahmad S Tajik.
    pdf

    We study the problem of fair division of a heterogeneous resource among strategic players. Given a divisible heterogeneous cake, we wish to divide the cake among n players in a way that meets the following criteria: (I) every player(weakly) prefers his allocated cake to any other player’s share (such notion is known as envy-freeness), (II) the mechanism is strategy-proof (truthful), and (III) the number of cuts made on the cake is minimal. We provide methods, namely expansion process and expansion process with unlocking, for dividing the cake under different assumptions on the valuation functions of the players.

  • C1
    Diversity Maximization via Composable Coresets.
    In CCCG 2015 -- Proceedings of 27th Canadian Conference on Computational Geometry, August 2015.
    With Sepideh Aghamolaei, and Hamid Zarrabi-Zadeh.
    pdf

    Given a set S of points in a metric space, and a diversity measure div (.) defined over subsets of S, the goal of the diversity maximization problem is to find a subset T of size k that maximizes div(T). Motivated by applications in massive data processing, we consider the composable coreset framework in which a coreset for a diversity measure is called composable, if for any collection of sets and their corresponding coresets, the maximum diversity of the union of the coresets approximates the maximum diversity of the union of the sets. We present composable coresets with near-optimal approximation factors for several notions of diversity, including remote-clique, remote-cycle, and remote-tree. We also prove a general lower bound on the approximation factor of composable coresets for a large class of diversity maximization problems.

Teaching

Graduate Teaching Assistant @ Georgia Institute of Technology

  • F2019
    Graduate Algorithms (CS6515)
  • S2019
    Graduate Algorithms (CS6515)
  • F2018
    Computability & Algorithms (CS6505)

Teaching Assistant @ Sharif University of Technology

  • F2016
    Design & Analysis of Algorithms (CE354)
  • S2016
    Artificial Intelligence (CE417), Data Structures & Algorithms (CE254)
  • S2015
    Advanced Programming (EE777), Data Structures & Algorithms (CE254)
  • F2014
    Artificial Intelligence (CE417)

Talks

On Rank Constrained Semideifinite Programming, CS Theory, CMU, Mar 2022

On Submodular Linear Ordering Problems, ACO, CMU, Oct 2021

Multiple Intents Scheduling, Two Sigma, Jul 2021

Warm Starts for Quantum Approximate Optimization Algorithm, INFORMS, Nov 2020

Minimum Sum Vertex Cover, Simons Institute for Theory of Computing, UC Berkeley, Oct 2020

Non-Convex Optimization Landscape of a Kernel PCA, Georgia Tech, Oct 2020

Generalized Min Sum Set Cover, ACO, Georgia Tech, Sep 2020

On Maximum Variance Embedding, Hot CSE Seminar, Georgia Tech, Dec 2019.

Service

Judge & Problem Design: IEEE International Programming Competition - IEEEXtreme 2020

Journal Review: IEEE Journal of Biomedical and Health Informatics 2018

Conference Review: Symposium on Computational Geometry 2016

Awards

Ranked 1st -- 9th IEEEXtreme International Programming Competition (2015, 2017)

Ranked 1st -- 20th National Scientific Olympiad in Computing. (2015)

Gold Medal -- 21st National Olympiad in Informatics. (2012)