The Experts below are selected from a list of 273135 Experts worldwide ranked by ideXlab platform
Shayan Oveis Gharan - One of the best experts on this subject based on the ideXlab platform.
-
graph clustering using Effective Resistance
Conference on Innovations in Theoretical Computer Science, 2018Co-Authors: Vedat Levi Alev, Nima Anari, Lap Chi Lau, Shayan Oveis GharanAbstract:We design a polynomial time algorithm that for any weighted undirected graph G = (V, E, w) and sufficiently large \delta > 1, partitions V into subsets V(1),..., V(h) for some h>= 1, such that at most \delta^{-1} fraction of the weights are between clusters, i.e. sum(i < j) |E(V(i), V(j)| < w(E)/\delta and the Effective Resistance diameter of each of the induced subgraphs G[V(i)] is at most \delta^3 times the inverse of the average weighted degree, i.e. max{ Reff(u, v) : u, v \in V(i)} < \delta^3 · |V|/w(E) for all i = 1,..., h. In particular, it is possible to remove one percent of weight of edges of any given graph such that each of the resulting connected components has Effective Resistance diameter at most the inverse of the average weighted degree. Our proof is based on a new connection between Effective Resistance and low conductance sets. We show that if the Effective Resistance between two vertices u and v is large, then there must be a low conductance cut separating u from v. This implies that very mildly expanding graphs have constant Effective Resistance diameter. We believe that this connection could be of independent interest in algorithm design.
-
graph clustering using Effective Resistance
arXiv: Data Structures and Algorithms, 2017Co-Authors: Vedat Levi Alev, Nima Anari, Lap Chi Lau, Shayan Oveis GharanAbstract:$ \def\vecc#1{\boldsymbol{#1}} $We design a polynomial time algorithm that for any weighted undirected graph $G = (V, E,\vecc w)$ and sufficiently large $\delta > 1$, partitions $V$ into subsets $V_1, \ldots, V_h$ for some $h\geq 1$, such that $\bullet$ at most $\delta^{-1}$ fraction of the weights are between clusters, i.e. \[ w(E - \cup_{i = 1}^h E(V_i)) \lesssim \frac{w(E)}{\delta};\] $\bullet$ the Effective Resistance diameter of each of the induced subgraphs $G[V_i]$ is at most $\delta^3$ times the average weighted degree, i.e. \[ \max_{u, v \in V_i} \mathsf{Reff}_{G[V_i]}(u, v) \lesssim \delta^3 \cdot \frac{|V|}{w(E)} \quad \text{ for all } i=1, \ldots, h.\] In particular, it is possible to remove one percent of weight of edges of any given graph such that each of the resulting connected components has Effective Resistance diameter at most the inverse of the average weighted degree. Our proof is based on a new connection between Effective Resistance and low conductance sets. We show that if the Effective Resistance between two vertices $u$ and $v$ is large, then there must be a low conductance cut separating $u$ from $v$. This implies that very mildly expanding graphs have constant Effective Resistance diameter. We believe that this connection could be of independent interest in algorithm design.
-
Effective Resistance reducing flows spectrally thin trees and asymmetric tsp
Foundations of Computer Science, 2015Co-Authors: Nima Anari, Shayan Oveis GharanAbstract:We show that the integrality gap of the natural LP relaxation of the Asymmetric Traveling Salesman Problem is polyloglog(n). In other words, there is a polynomial time algorithm that approximates the value of the optimum tour within a factor of polyloglog(n), where polyloglog(n) is a bounded degree polynomial of log log(n). We prove this by showing that any k-edge-connected unweighted graph has a polyloglog(n)/k-thin spanning tree. Our main new ingredient is a procedure, albeit an exponentially sized convex program, that "transforms" graphs that do not admit any spectrally thin trees into those that provably have spectrally thin trees. More precisely, given a k-edge-connected graph G=(V, E) where k>= 7log(n), we show that there is a matrix D that "preserves" the structure of all cuts of G such that for a subset F of E that induces an O(k)-edge-connected graph, the Effective Resistance of every edge in F w.r.t. D is at most polylog(k)/k. Then, we use our recent extension of the seminal work of Marcus, Spiel man, and Srivastava [MSS13] to prove the existence of a polylog(k)/k-spectrally thin tree with respect to D. Such a tree is polylog(k)/k-combinatorially thin with respect to G as D preserves the structure of cuts of G.
-
Effective Resistance reducing flows spectrally thin trees and asymmetric tsp
arXiv: Data Structures and Algorithms, 2014Co-Authors: Nima Anari, Shayan Oveis GharanAbstract:We show that the integrality gap of the natural LP relaxation of the Asymmetric Traveling Salesman Problem is $\text{polyloglog}(n)$. In other words, there is a polynomial time algorithm that approximates the value of the optimum tour within a factor of $\text{polyloglog}(n)$, where $\text{polyloglog}(n)$ is a bounded degree polynomial of $\log\log(n)$. We prove this by showing that any $k$-edge-connected unweighted graph has a $\text{polyloglog}(n)/k$-thin spanning tree. Our main new ingredient is a procedure, albeit an exponentially sized convex program, that "transforms" graphs that do not admit any spectrally thin trees into those that provably have spectrally thin trees. More precisely, given a $k$-edge-connected graph $G=(V,E)$ where $k\geq 7\log(n)$, we show that there is a matrix $D$ that "preserves" the structure of all cuts of $G$ such that for a set $F\subseteq E$ that induces an $\Omega(k)$-edge-connected graph, the Effective Resistance of every edge in $F$ w.r.t. $D$ is at most $\text{polylog}(k)/k$. Then, we use a recent extension of the seminal work of Marcus, Spielman, and Srivastava [MSS13] by the authors [AO14] to prove the existence of a $\text{polylog}(k)/k$-spectrally thin tree with respect to $D$. Such a tree is $\text{polylog}(k)/k$-combinatorially thin with respect to $G$ as $D$ preserves the structure of cuts of $G$.
Naomi Ehrich Leonard - One of the best experts on this subject based on the ideXlab platform.
-
A New Notion of Effective Resistance for Directed Graphs - Part I: Definition and Properties
IEEE Transactions on Automatic Control, 2016Co-Authors: George Forrest Young, Luca Scardovi, Naomi Ehrich LeonardAbstract:The graphical notion of Effective Resistance has found wide-ranging applications in many areas of pure mathematics, applied mathematics and control theory. By the nature of its construction, Effective Resistance can only be computed in undirected graphs and yet in several areas of its application, directed graphs arise as naturally (or more naturally) than undirected ones. In part I of this work, we propose a generalization of Effective Resistance to directed graphs that preserves its control-theoretic properties in relation to consensus-type dynamics. We proceed to analyze the dependence of our algebraic definition on the structural properties of the graph and the relationship between our construction and a graphical distance. The results make possible the calculation of Effective Resistance between any two nodes in any directed graph and provide a solid foundation for the application of Effective Resistance to problems involving directed graphs.
-
a new notion of Effective Resistance for directed graphs part ii computing Resistances
arXiv: Optimization and Control, 2013Co-Authors: George Forrest Young, Luca Scardovi, Naomi Ehrich LeonardAbstract:In Part I of this work we defined a generalization of the concept of Effective Resistance to directed graphs, and we explored some of the properties of this new definition. Here, we use the theory developed in Part I to compute Effective Resistances in some prototypical directed graphs. This exploration highlights cases where our notion of Effective Resistance for directed graphs behaves analogously to our experience from undirected graphs, as well as cases where it behaves in unexpected ways.
Nima Anari - One of the best experts on this subject based on the ideXlab platform.
-
graph clustering using Effective Resistance
Conference on Innovations in Theoretical Computer Science, 2018Co-Authors: Vedat Levi Alev, Nima Anari, Lap Chi Lau, Shayan Oveis GharanAbstract:We design a polynomial time algorithm that for any weighted undirected graph G = (V, E, w) and sufficiently large \delta > 1, partitions V into subsets V(1),..., V(h) for some h>= 1, such that at most \delta^{-1} fraction of the weights are between clusters, i.e. sum(i < j) |E(V(i), V(j)| < w(E)/\delta and the Effective Resistance diameter of each of the induced subgraphs G[V(i)] is at most \delta^3 times the inverse of the average weighted degree, i.e. max{ Reff(u, v) : u, v \in V(i)} < \delta^3 · |V|/w(E) for all i = 1,..., h. In particular, it is possible to remove one percent of weight of edges of any given graph such that each of the resulting connected components has Effective Resistance diameter at most the inverse of the average weighted degree. Our proof is based on a new connection between Effective Resistance and low conductance sets. We show that if the Effective Resistance between two vertices u and v is large, then there must be a low conductance cut separating u from v. This implies that very mildly expanding graphs have constant Effective Resistance diameter. We believe that this connection could be of independent interest in algorithm design.
-
graph clustering using Effective Resistance
arXiv: Data Structures and Algorithms, 2017Co-Authors: Vedat Levi Alev, Nima Anari, Lap Chi Lau, Shayan Oveis GharanAbstract:$ \def\vecc#1{\boldsymbol{#1}} $We design a polynomial time algorithm that for any weighted undirected graph $G = (V, E,\vecc w)$ and sufficiently large $\delta > 1$, partitions $V$ into subsets $V_1, \ldots, V_h$ for some $h\geq 1$, such that $\bullet$ at most $\delta^{-1}$ fraction of the weights are between clusters, i.e. \[ w(E - \cup_{i = 1}^h E(V_i)) \lesssim \frac{w(E)}{\delta};\] $\bullet$ the Effective Resistance diameter of each of the induced subgraphs $G[V_i]$ is at most $\delta^3$ times the average weighted degree, i.e. \[ \max_{u, v \in V_i} \mathsf{Reff}_{G[V_i]}(u, v) \lesssim \delta^3 \cdot \frac{|V|}{w(E)} \quad \text{ for all } i=1, \ldots, h.\] In particular, it is possible to remove one percent of weight of edges of any given graph such that each of the resulting connected components has Effective Resistance diameter at most the inverse of the average weighted degree. Our proof is based on a new connection between Effective Resistance and low conductance sets. We show that if the Effective Resistance between two vertices $u$ and $v$ is large, then there must be a low conductance cut separating $u$ from $v$. This implies that very mildly expanding graphs have constant Effective Resistance diameter. We believe that this connection could be of independent interest in algorithm design.
-
Effective Resistance reducing flows spectrally thin trees and asymmetric tsp
Foundations of Computer Science, 2015Co-Authors: Nima Anari, Shayan Oveis GharanAbstract:We show that the integrality gap of the natural LP relaxation of the Asymmetric Traveling Salesman Problem is polyloglog(n). In other words, there is a polynomial time algorithm that approximates the value of the optimum tour within a factor of polyloglog(n), where polyloglog(n) is a bounded degree polynomial of log log(n). We prove this by showing that any k-edge-connected unweighted graph has a polyloglog(n)/k-thin spanning tree. Our main new ingredient is a procedure, albeit an exponentially sized convex program, that "transforms" graphs that do not admit any spectrally thin trees into those that provably have spectrally thin trees. More precisely, given a k-edge-connected graph G=(V, E) where k>= 7log(n), we show that there is a matrix D that "preserves" the structure of all cuts of G such that for a subset F of E that induces an O(k)-edge-connected graph, the Effective Resistance of every edge in F w.r.t. D is at most polylog(k)/k. Then, we use our recent extension of the seminal work of Marcus, Spiel man, and Srivastava [MSS13] to prove the existence of a polylog(k)/k-spectrally thin tree with respect to D. Such a tree is polylog(k)/k-combinatorially thin with respect to G as D preserves the structure of cuts of G.
-
Effective Resistance reducing flows spectrally thin trees and asymmetric tsp
arXiv: Data Structures and Algorithms, 2014Co-Authors: Nima Anari, Shayan Oveis GharanAbstract:We show that the integrality gap of the natural LP relaxation of the Asymmetric Traveling Salesman Problem is $\text{polyloglog}(n)$. In other words, there is a polynomial time algorithm that approximates the value of the optimum tour within a factor of $\text{polyloglog}(n)$, where $\text{polyloglog}(n)$ is a bounded degree polynomial of $\log\log(n)$. We prove this by showing that any $k$-edge-connected unweighted graph has a $\text{polyloglog}(n)/k$-thin spanning tree. Our main new ingredient is a procedure, albeit an exponentially sized convex program, that "transforms" graphs that do not admit any spectrally thin trees into those that provably have spectrally thin trees. More precisely, given a $k$-edge-connected graph $G=(V,E)$ where $k\geq 7\log(n)$, we show that there is a matrix $D$ that "preserves" the structure of all cuts of $G$ such that for a set $F\subseteq E$ that induces an $\Omega(k)$-edge-connected graph, the Effective Resistance of every edge in $F$ w.r.t. $D$ is at most $\text{polylog}(k)/k$. Then, we use a recent extension of the seminal work of Marcus, Spielman, and Srivastava [MSS13] by the authors [AO14] to prove the existence of a $\text{polylog}(k)/k$-spectrally thin tree with respect to $D$. Such a tree is $\text{polylog}(k)/k$-combinatorially thin with respect to $G$ as $D$ preserves the structure of cuts of $G$.
Matthew N Rouse - One of the best experts on this subject based on the ideXlab platform.
-
complementary epistasis involving sr12 explains adult plant Resistance to stem rust in thatcher wheat triticum aestivum l
Theoretical and Applied Genetics, 2014Co-Authors: Matthew N Rouse, L E Talbert, Davinder Singh, J D ShermanAbstract:Key message Quantitative trait loci conferring adult plant Resistance to Ug99 stem rust in Thatcher wheat display complementary gene action suggesting multiple quantitative trait loci are needed for Effective Resistance. Abstract Adult plant Resistance (APr) in wheat (Triticum aestivum l.) to stem rust, caused by Puccinia graminis f. sp. tritici (Pgt), is desirable because this Resistance can be Pgt race non-specific. Resistance derived from cultivar Thatcher can confer high levels of APr to the virulent Pgt race TTKSK (Ug99) when combined with stem rust resist- ance gene Sr57 (Lr34). To identify the loci conferring APr in Thatcher, we evaluated 160 rIls derived from Thatcher crossed to susceptible cultivar Mcneal for field stem rust
Thomas Ederth - One of the best experts on this subject based on the ideXlab platform.
-
hydration and chain entanglement determines the optimum thickness of poly hema co peg ma brushes for Effective Resistance to settlement and adhesion of marine fouling organisms
ACS Applied Materials & Interfaces, 2014Co-Authors: Wetra Yandi, Sophie Mieszkin, Pierre Martintanchereau, Maureen E Callow, James A Callow, Lyndsey Tyson, Bo Liedberg, Thomas EderthAbstract:Understanding how surface physicochemical properties influence the settlement and adhesion of marine fouling organisms is important for the development of Effective and environmentally benign marine antifouling coatings. We demonstrate that the thickness of random poly(HEMA-co-PEG10MA) copolymer brushes affect antifouling behavior. Films of thicknesses ranging from 50 to 1000 A were prepared via surface-initiated atom-transfer radical polymerization and characterized using infrared spectroscopy, ellipsometry, atomic force microscopy and contact angle measurements. The fouling Resistance of these films was investigated by protein adsorption, attachment of the marine bacterium Cobetia marina, settlement and strength of attachment tests of zoospores of the marine alga Ulva linza and static immersion field tests. These assays show that the polymer film thickness influenced the antifouling performance, in that there is an optimum thickness range, 200–400 A (dry thickness), where fouling of all types, as well a...
