Result page:
1
2
3
4
5
1
A new approach to computing maximum flows using electrical flows
Yin Tat Lee,
Satish Rao,
Nikhil Srivastava
June 2013
STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of computing
Publisher: ACM
Bibliometrics:
Citation Count: 6
Downloads (6 Weeks): 6, Downloads (12 Months): 53, Downloads (Overall): 336
Full text available:
PDF
We give an algorithm which computes a (1-ε)-approximately maximum st-flow in an undirected uncapacitated graph in time O(1/ε√m/F⋅ m log 2 n) where F is the flow value. By trading this off against the Karger-Levine algorithm for undirected graphs which takes ~O(m+nF) time, we obtain a running time of ~O(m ...
Keywords:
electrical flow, maximum flow, nesterov, minimum cut
2
Query strategies for evading convex-inducing classifiers
May 2012
The Journal of Machine Learning Research: Volume 13, 3/1/2012
Publisher: JMLR.org
Bibliometrics:
Citation Count: 15
Downloads (6 Weeks): 1, Downloads (12 Months): 7, Downloads (Overall): 66
Full text available:
PDF
Classifiers are often used to detect miscreant activities. We study how an adversary can systematically query a classifier to elicit information that allows the attacker to evade detection while incurring a near-minimal cost of modifying their intended malfeasance. We generalize the theory of Lowd and Meek (2005) to the family ...
Keywords:
reverse engineering, query algorithms, evasion, adversarial learning
Also published in:
January 2012
The Journal of Machine Learning Research: Volume 13 Issue 1, January 2012
3
Quartets MaxCut: A Divide and Conquer Quartets Algorithm
Sagi Snir,
Satish Rao
October 2010
IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB): Volume 7 Issue 4, October 2010
Publisher: IEEE Computer Society Press
Bibliometrics:
Citation Count: 12
Downloads (6 Weeks): 1, Downloads (12 Months): 10, Downloads (Overall): 124
Full text available:
PDF
Accurate phylogenetic reconstruction methods are currently limited to a maximum of few dozens of taxa. Supertree methods construct a large tree over a large set of taxa, from a set of small trees over overlapping subsets of the complete taxa set. Hence, in order to construct the tree of life ...
Keywords:
Phylogenetic reconstruction, quartets, MaxCut, supertree.
4
ℓ22 Spreading Metrics for Vertex Ordering Problems
April 2010
Algorithmica: Volume 56 Issue 4, April 2010
Publisher: Springer-Verlag New York, Inc.
We design approximation algorithms for the vertex ordering problems Minimum Linear Arrangement, Minimum Containing Interval Graph, and Minimum Storage-Time Product, achieving approximation factors of $O(\sqrt{\log n}\log\log n)$ , $O(\sqrt{\log n}\log\log n)$ , and $O(\sqrt{\log T}\log\log T)$ , respectively, the last running in time polynomial in T (T being the sum ...
Keywords:
Approximation algorithm, Minimum storage-time product, Minimum linear arrangement, Semidefinite programming, Vertex ordering problem, Minimum containing interval graph
5
Eigenvalue bounds, spectral partitioning, and metrical deformations via flows
Punyashloka Biswal,
James R. Lee,
Satish Rao
March 2010
Journal of the ACM (JACM): Volume 57 Issue 3, March 2010
Publisher: ACM
Bibliometrics:
Citation Count: 9
Downloads (6 Weeks): 3, Downloads (12 Months): 33, Downloads (Overall): 601
Full text available:
PDF
We present a new method for upper bounding the second eigenvalue of the Laplacian of graphs. Our approach uses multi-commodity flows to deform the geometry of the graph; we embed the resulting metric into Euclidean space to recover a bound on the Rayleigh quotient. Using this, we show that every ...
Keywords:
network flows, spectral graph theory, Metric embeddings
6
ℓ 22 Spreading Metrics for Vertex Ordering Problems
January 2010
Algorithmica: Volume 56 Issue 4, April 2010
Publisher: Springer-Verlag New York, Inc.
We design approximation algorithms for the vertex ordering problems Minimum Linear Arrangement , Minimum Containing Interval Graph , and Minimum Storage-Time Product , achieving approximation factors of $O(\sqrt{\log n}\log\log n)$, $O(\sqrt{\log n}\log\log n)$, and $O(\sqrt{\log T}\log\log T)$, respectively, the last running in time polynomial in T ( T being the ...
Keywords:
Semidefinite programming, Vertex ordering problem, Minimum containing interval graph, Approximation algorithm, Minimum storage-time product, Minimum linear arrangement
7
Edge Disjoint Paths in Moderately Connected Graphs
Satish Rao,
Shuheng Zhou
January 2010
SIAM Journal on Computing: Volume 39 Issue 5, January 2010
Publisher: Society for Industrial and Applied Mathematics
We study the edge disjoint paths (EDP) problem in undirected graphs: Given a graph $G$ with $n$ nodes and a set $\mathcal{T}$ of pairs of terminals, connect as many terminal pairs as possible using paths that are mutually edge disjoint. This leads to a variety of classic NP-complete problems, for ...
Keywords:
polylogarithmic approximation, edge disjoint paths, random sampling in cuts
8
Edge Disjoint Paths in Moderately Connected Graphs
Satish Rao,
Shuheng Zhou
January 2010
SIAM Journal on Computing: Volume 39 Issue 5, January 2010
Publisher: Society for Industrial and Applied Mathematics
We study the edge disjoint paths (EDP) problem in undirected graphs: Given a graph $G$ with $n$ nodes and a set $\mathcal{T}$ of pairs of terminals, connect as many terminal pairs as possible using paths that are mutually edge disjoint. This leads to a variety of classic NP-complete problems, for ...
Keywords:
edge disjoint paths, random sampling in cuts, polylogarithmic approximation
9
ANTIDOTE: understanding and defending against poisoning of anomaly detectors
November 2009
IMC '09: Proceedings of the 9th ACM SIGCOMM conference on Internet measurement
Publisher: ACM
Bibliometrics:
Citation Count: 32
Downloads (6 Weeks): 11, Downloads (12 Months): 60, Downloads (Overall): 612
Full text available:
PDF
Statistical machine learning techniques have recently garnered increased popularity as a means to improve network design and security. For intrusion detection, such methods build a model for normal behavior from training data and detect attacks as deviations from that model. This process invites adversaries to manipulate the training data so ...
Keywords:
network traffic analysis, adversarial learning, principal components analysis, robust statistics
10
Stealthy poisoning attacks on PCA-based anomaly detectors
October 2009
ACM SIGMETRICS Performance Evaluation Review: Volume 37 Issue 2, September 2009
Publisher: ACM
Bibliometrics:
Citation Count: 4
Downloads (6 Weeks): 6, Downloads (12 Months): 28, Downloads (Overall): 177
Full text available:
PDF
We consider systems that use PCA-based detectors obtained from a comprehensive view of the network's traffic to identify anomalies in backbone networks. To assess these detectors' susceptibility to adversaries wishing to evade detection, we present and evaluate short-term and long-term data poisoning schemes that trade-off between poisoning duration and the ...
Keywords:
adversarial learning, principal components analysis, network traffic analysis
11
A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids
October 2009
Theoretical Computer Science: Volume 410 Issue 44, October, 2009
Publisher: Elsevier Science Publishers Ltd.
In the minimum-degree minimum spanning tree (MDMST) problem, we are given a graph G, and the goal is to find a minimum spanning tree (MST) T, such that the maximum degree of T is as small as possible. This problem is NP-hard and generalizes the Hamiltonian path problem. We give ...
Keywords:
Approximation algorithms, Push-relabel, Degree-bounded network design, Spanning trees
12
Graph partitioning using single commodity flows
July 2009
Journal of the ACM (JACM): Volume 56 Issue 4, June 2009
Publisher: ACM
Bibliometrics:
Citation Count: 21
Downloads (6 Weeks): 12, Downloads (12 Months): 64, Downloads (Overall): 1,043
Full text available:
PDF
We show that the sparsest cut in graphs with n vertices and m edges can be approximated within O (log 2 n ) factor in Õ( m + n 3/2 ) time using polylogarithmic single commodity max-flow computations. Previous algorithms are based on multicommodity flows that take time Õ( m ...
Keywords:
spectral method, sparse cut, Edge-separator, single commodity max-flow
13
What Would Edmonds Do? Augmenting Paths and Witnesses for Degree-Bounded MSTs
May 2009
Algorithmica: Volume 55 Issue 1, May 2009
Publisher: Springer-Verlag New York, Inc.
Given a graph and degree upper bounds on vertices, the BDMST problem requires us to find a minimum cost spanning tree respecting the given degree bounds. This problem generalizes the Travelling Salesman Path Problem (TSPP), even in unweighted graphs, and so we expect that it is necessary to relax the ...
Keywords:
Combinatorial optimization, Matching, Minimum spanning trees, Approximation algorithms
14
Expander flows, geometric embeddings and graph partitioning
Sanjeev Arora,
Satish Rao,
Umesh Vazirani
April 2009
Journal of the ACM (JACM): Volume 56 Issue 2, April 2009
Publisher: ACM
Bibliometrics:
Citation Count: 81
Downloads (6 Weeks): 22, Downloads (12 Months): 157, Downloads (Overall): 2,139
Full text available:
PDF
We give a O (&sqrt;log n )-approximation algorithm for the sparsest cut, edge expansion, balanced separator, and graph conductance problems. This improves the O (log n )-approximation of Leighton and Rao (1988). We use a well-known semidefinite relaxation with triangle inequality constraints. Central to our analysis is a geometric theorem ...
Keywords:
Graph partitioning, graph separators, semidefinite programs, expanders, expansion, multicommodity flows
15
Eigenvalue Bounds, Spectral Partitioning, and Metrical Deformations via Flows
Punyashloka Biswal,
James R. Lee,
Satish Rao
October 2008
FOCS '08: Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science
Publisher: IEEE Computer Society
We present a new methodfor upper bounding the second eigenvalue of theLaplacian of graphs.Our approach uses multi-commodity flows to deform the geometry of the graph;we embed the resulting metric into Euclidean spaceto recover a bound on the Rayleigh quotient.Using this, we show that every $n$-vertexgraphof genus $g$ and maximum degree ...
16
Geometry, flows, and graph-partitioning algorithms
Sanjeev Arora,
Satish Rao,
Umesh Vazirani
October 2008
Communications of the ACM: Volume 51 Issue 10, October 2008
Publisher: ACM
Bibliometrics:
Citation Count: 6
Downloads (6 Weeks): 12, Downloads (12 Months): 66, Downloads (Overall): 1,341
Full text available:
Html
PDF
17
The k-traveling repairmen problem
Jittat Fakcharoenphol,
Chris Harrelson,
Satish Rao
November 2007
ACM Transactions on Algorithms (TALG): Volume 3 Issue 4, November 2007
Publisher: ACM
Bibliometrics:
Citation Count: 8
Downloads (6 Weeks): 12, Downloads (12 Months): 54, Downloads (Overall): 858
Full text available:
PDF
We consider the k -traveling repairmen problem, also known as the minimum latency problem, to multiple repairmen. We give a polynomial-time 8.497α-approximation algorithm for this generalization, where α denotes the best achievable approximation factor for the problem of finding the least-cost rooted tree spanning i vertices of a metric. For ...
Keywords:
vehicle routing, Traveling salesman
18
A Nearly Linear-Time Approximation Scheme for the Euclidean $k$-Median Problem
Stavros G. Kolliopoulos,
Satish Rao
June 2007
SIAM Journal on Computing: Volume 37 Issue 3, June 2007
Publisher: Society for Industrial and Applied Mathematics
This paper provides a randomized approximation scheme for the $k$-median problem when the input points lie in the $d$-dimensional Euclidean space. The worst-case running time is $O(2^{O((\log(1/\epsilon) / \varepsilon)^{d-1})} n \log^{d+6} n ),$ which is nearly linear for any fixed $\varepsilon$ and $d$. Moreover, our method provides the first polynomial-time ...
Keywords:
$k$-median, Euclidean space, approximation algorithms, approximation schemes, facility location, linear time
19
An efficient and accurate graph-based approach to detect population substructure
April 2007
RECOMB'07: Proceedings of the 11th annual international conference on Research in computational molecular biology
Publisher: Springer-Verlag
Currently, large-scale projects are underway to perform whole genome disease association studies. Such studies involve the genotyping of hundreds of thousands of SNP markers. One of the main obstacles in performing such studies is that the underlying population substructure could artificially inflate the p -values, thereby generating a lot of ...
20
A rigorous analysis of population stratification with limited data
January 2007
SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms
Publisher: Society for Industrial and Applied Mathematics
Bibliometrics:
Citation Count: 4
Downloads (6 Weeks): 2, Downloads (12 Months): 5, Downloads (Overall): 178
Full text available:
PDF
Finding the genetic factors of complex diseases such as cancer, currently a major effort of the international community, will potentially lead to better treatment of these diseases. One of the major difficulties in these studies, is the fact that the genetic components of an individual not only depend on the ...
Author only
