Milena Mihail

FOCS Conference 2006 Conference Paper

A Local Switch Markov Chain on Given Degree Graphs with Application in Connectivity of Peer-to-Peer Networks

• Tomás Feder
• Adam Guetz
• Milena Mihail
• Amin Saberi

We study a switch Markov chain on regular graphs, where switches are allowed only between links that are at distance 2; we call this the flip. The motivation for studying the flip Markov chain arises in the context of unstructured peer-to-peer networks, which constantly perform such flips in an effort to randomize. We show that the flip Markov chain on regular graphs is rapidly mixing, thus justifying this widely used peer-to-peer networking practice. Our mixing argument uses the Markov chain comparison technique. In particular, we extend this technique to embedding arguments where the compared Markov chains are defined on different state spaces. We give several conditions which generalize our results beyond regular graphs

FOCS Conference 2003 Conference Paper

On Certain Connectivity Properties of the Internet Topology

• Milena Mihail
• Christos H. Papadimitriou
• Amin Saberi

We show that random graphs in the preferential connectivity model have constant conductance, and hence have worst-case routing congestion that scales logarithmically with the number of nodes. Another immediate implication is constant spectral gap between the first and second eigenvalues of the random walk matrix associated with these graphs. We also show that the expected frugality (overpayment in the Vickrey-Clarke-Groves mechanism for shortest paths) of a random graph is bounded by a small constant.

SODA Conference 2002 Conference Paper

Caching with expiration times

• Parikshit Gopalan
• Howard J. Karloff
• Aranyak Mehta
• Milena Mihail
• Nisheeth K. Vishnoi

TCS Journal 1999 Journal Article

Optimal wavelength routing on directed fiber trees

• Thomas Erlebach
• Klaus Jansen
• Christos Kaklamanis
• Milena Mihail
• Pino Persiano

We present a polynomial-time greedy algorithm that assigns proper wavelengths to a set of requests of maximum load L per directed fiber link on a directed fiber tree using at most 5/3L wavelengths. This improves previous results of Raghavan and Upfal (Proc. Ann. ACM Symp. on theory of computing STOC, 1994, pp. 134–143), Mihail et al. (Proc. 36th IEEE Symp. on Foundations of Computer Science, 1995, pp. 548–557), Kaklamanis and Persiano (Proc. Algorithms — ESA 96, Lecture Notes in Computer Science, 1136, pp. 460–470), Kumar and Schwabe (Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms SODA, 1997, pp. 437–444). We also prove that no greedy algorithm can in general use less than 5/3L wavelengths for a set of requests of load L in a directed fiber tree, and thus our algorithm is optimal in the class of greedy algorithms which includes the algorithms presented in [8–10, 12].

SODA Conference 1996 Conference Paper

A Commercial Application of Survivable Network Design: ITP/INPLANS CCS Network Topology Analyzer

• Milena Mihail
• David Shallcross
• Nate Dean
• Marco Mostrel

FOCS Conference 1995 Conference Paper

Efficient Access to Optical Bandwidth - Wavelength Routing on Directed Fiber Trees, Rings, and Trees of Rings

• Milena Mihail
• Christos Kaklamanis
• Satish Rao

We address efficient access to bandwidth in WDM (wavelength division multiplexing) optical networks. We consider tree topologies, ring topologies, as well as trees of rings. These are topologies of concrete practical relevance for which undirected underlying graph models have been studied before by P. Raghavan and E. Upfal (1993). As opposed to previous studies (A. Aggarwal et al. , 1993; R. Pankaj, 1992; P. Raghavan and E. Upfal, 1993), we consider directed graph models. Directedness of fiber links is dictated by physical directedness of optical amplifiers. For trees, we give a polynomial time routing algorithm that satisfies requests of maximum load L/sub max/ per fiber link using no more than 15L/sub max//8/spl les/15OPT/8 optical wavelengths. This improves a 2L/sub max/ scheme that is implicit by P. Raghavan and E. Upfal by extending their undirected methods to our directed model. Alternatively stated, for fixed W wavelength technology, we can load the network up to L, , 8W/15 rather than W/2. In engineering terms, this is a so called "6. 66% increase of bandwidth" and it is considered substantial. For rings, the approximation factor is 2OPT. For trees of rings, the approximation factor is 15OPT/4. Technically, optical routing requirements give rise to novel coloring paradigms. Our algorithms involve matchings and multicolored alternating cycles, combined with detailed potential and averaging analysis.

STOC Conference 1993 Conference Paper

A primal-dual approximation algorithm for generalized Steiner network problems

• David P. Williamson
• Michel X. Goemans
• Milena Mihail
• Vijay V. Vazirani

STOC Conference 1992 Conference Paper

Balanced Matroids

• Tomás Feder
• Milena Mihail

MFCS Conference 1992 Invited Paper

On the Expansion of Combinatorial Polytopes

• Milena Mihail

Abstract Strong expansion properties have been established fot several classes of graphs that can be expressed as the 1-skeletons of 0–1 polytopes. These include graphs associated with, matchings, older ideals, independent sets, and balanced matroids (e. g. for the graphic matroid). The question whether these are examples of a more general phenomenon has been raizeD: “Do all 0–1 polytopes have cutset expansion at least 1? ” A positive answer to the above question (even in weaker or more special form), implies efficient randomized algorithms to approximate a vast class of N P -hard counting problems.

SODA Conference 1992 Conference Paper

On the Number of Eularian Orientations of a Graph

• Milena Mihail
• Peter Winkler 0001

SODA Conference 1991 Conference Paper

Learning the Fourier Spectrum of Probabilistic Lists and Trees

• William Aiello
• Milena Mihail

FOCS Conference 1989 Conference Paper

Conductance and Convergence of Markov Chains-A Combinatorial Treatment of Expanders

• Milena Mihail

A direct combinatorial argument is given to bound the convergence rate of Markov chains in terms of their conductance (these are statements of the nature 'random walks on expanders converge fast'). In addition to showing that the linear algebra in previous arguments for such results on time-reversible Markov chains was unnecessary, the direct analysis applies to general irreversible Markov chains. >

FOCS Conference 1988 Conference Paper

Polytopes, Permanents and Graphs with Large Factors

• Paul Dagum
• Michael Luby
• Milena Mihail
• Umesh V. Vazirani

Randomized algorithms for approximating the number of perfect matchings in a graph are considered. An algorithm that is a natural simplification of one suggested and analyzed previously is introduced and analyzed. One of the key ideas is to view the analysis from a geometric perspective: it is proved that for any graph G the k-slice of the well-known Edmonds matching polytope has magnification 1. For a bipartite graph G=(U, V, E), mod U mod = mod V mod =n, with d edge-disjoint perfect matchings, it is proved that the ratio of the number of almost perfect matchings to the number of perfect matchings is at most n/sup 3n/d/. For any constant alpha >0 this yields a a fully polynomial randomized algorithm for approximating the number of perfect matchings in bipartite graphs with d>or= alpha n. Moreover, for some constant c>0 it is the fastest known approximation algorithm for bipartite graphs with d>or= clog n. >