Search

Your search keyword '"UPFAL, ELI"' showing total 512 results
Start Over Author "UPFAL, ELI"
512 results on '"UPFAL, ELI"'

157. Probabilistic analysis of the k-server problem on the circle

Author

Anagnostopoulos, Aris, Dombry, Clément, Guillotin-Plantard, Nadine, Kontoyiannis, Ioannis, Upfal, Eli, Department of Computer and Systems Science [Rome], Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome], Institut Camille Jordan [Villeurbanne] (ICJ), École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université Jean Monnet [Saint-Étienne] (UJM)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Department of Informatics, Department of Informatics Athens Univ of Econ & Business Patission 76, Athens 10434, Greece, Department of Computer Science (Brown University), and Brown University

Subjects
[MATH.MATH-PR]Mathematics [math]/Probability [math.PR], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2010

158. 07391 Abstracts Collection ��� Probabilistic Methods in the Design and Analysis of Algorithms

Author

Dietzfelbinger, Martin, Teng, Shang-Hua, Upfal, Eli, and V��cking, Berthold

Subjects
Probabilistic analysis, Randomization, Complexity, Algorithms
Abstract

From 23.09.2007 to 28.09.2007, the Dagstuhl Seminar 07391 "Probabilistic Methods in the Design and Analysis of Algorithms''was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. The seminar brought together leading researchers in probabilistic methods to strengthen and foster collaborations among various areas of Theoretical Computer Science. The interaction between researchers using randomization in algorithm design and researchers studying known algorithms and heuristics in probabilistic models enhanced the research of both groups in developing new complexity frameworks and in obtaining new algorithmic results. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Published
2007
Full Text
View/download PDF

162. TRIÈST: Counting Local and Global Triangles in Fully Dynamic Streams with Fixed Memory Size.

Author

DE STEFANI, LORENZO, EPASTO, ALESSANDRO, RIONDATO, MATTEO, and UPFAL, ELI

Subjects
PROBABILISTIC inference, COMPUTATIONAL number theory, GRAPH theory, KNOT insertion & deletion algorithms, DATA mining, MATHEMATICAL models
Abstract

We present TRIÈST, a suite of one-pass streaming algorithms to compute unbiased, low-variance, highquality approximations of the global and local (i.e., incident to each vertex) number of triangles in a fully dynamic graph represented as an adversarial stream of edge insertions and deletions. Our algorithms use reservoir sampling and its variants to exploit the user-specified memory space at all times. This is in contrast with previous approaches, which require hard-to-choose parameters (e.g., a fixed sampling probability) and offer no guarantees on the amount of memory they use. We analyze the variance of the estimations and show novel concentration bounds for these quantities. Our experimental results on very large graphs demonstrate that TRIÈST outperforms state-of-the-art approaches in accuracy and exhibits a small update time. [ABSTRACT FROM AUTHOR]

Published
2017
Full Text
View/download PDF

169. The generalized packet routing problem

Author

Peleg, David and Upfal, Eli

Subjects
Packet Switch, Routing, Algorithm Analysis, Communications Technology, New Technique, Parallel Transmission, Distributed Systems, Load Balancing, Token Passing, Permutations, Network Architecture, Optimization
Published
1987

172. Algorithmic Principles1.

Author

Arumugam, Guru Prakash, Augustine, John, Upfal, Eli, Parishkrati, Srikanthan, Prashanth, Palem, Krishna, Bhargava, Ayush, and Yenugula, Sreelatha

Published
2015

174. PARMA

Author

Riondato, Matteo, primary, DeBrabant, Justin A., additional, Fonseca, Rodrigo, additional, and Upfal, Eli, additional

Published
2012
Full Text
View/download PDF

195. Existence and construction of edge disjoint paths on expander graphs

Author

Broder, Andrei Zary., Frieze, and Upfal, Eli

Subjects
FOS: Mathematics, 19999 Mathematical Sciences not elsewhere classified, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

"Given an expander graph G = (V,E) and a set of K disjoint pairs of vertices in V, we are interested in finding for each pair (a[subscript i], b[subscript i]), a path connecting a[subscript i] to b[subscript i], such that the set of K paths so found is edge disjoint. (For general graphs the related decision problem is NP-complete.) We prove sufficient conditions for the existence of K [< or =] n/(log n)[superscript K] edge disjoint paths connecting any set of K disjoint pairs of vertices on any n vertex bounded degree expander, where K depends only on the expansion properties of the input graph, and not on n. Furthermore, we present a randomizedo(n┬│) [sic] time algorithm, and a random NC algorithm forconstructing [sic] these paths. (Previous existence proofs and construction algorithms allowed only up to n[superscript epsilon] pairs, for some [epsilon] << 1/3, and strong expanders [17].) In passing, we develop an algorithm for splitting a sufficiently strong expander into two edge disjoint spanning expanders."

Published
1992
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results