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.
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)
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.
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
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.
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.
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.
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.
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.
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.
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.
In Transactions on Algorithms (TALG) 2021.
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.
University of Illinois at Urbana-Champaign Theory Seminar, April 19.
University of Washington Theory Seminar, April 20.
Joint Purdue University and University of Michigan Theory Seminar, April 23.
TOC4Fairness Seminar, April 28.
MIT A&C Seminar, May 10.
UC San Diego Theory Seminar, May 17.
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.