Press "Enter" to skip to content

Algorithms and Computation: 11th International Conference, by Jean-Daniel Boissonnat (auth.), Gerhard Goos, Juris

By Jean-Daniel Boissonnat (auth.), Gerhard Goos, Juris Hartmanis, Jan van Leeuwen, D. T. Lee, Shang-Hua Teng (eds.)

The papers during this quantity have been chosen for presentation on the 11th Annual foreign Symposium on Algorithms and Computation (ISAAC 2000), hung on 18{20 December, 2000 on the Institute of data technology, Academia Sinica, Taipei, Taiwan. prior conferences have been held in Tokyo (1990), Taipei (1991), Nagoya (1992), Hong Kong (1993), Beijing (1994), Cairns (1995), Osaka (1996), Singapore (1997), Taejon (1998), and Chennai (1999). Submissions to the convention this 12 months have been carried out completely electro- cally. due to the superb software program built through the Institute of data technological know-how, Academia Sinica, we have been capable of perform almost all conversation through the realm broad internet. in accordance with the decision for papers, a complete of 87 prolonged abstracts have been submitted from 25 international locations. every one submitted paper was once dealt with by means of no less than 3 application committee individuals, with the help of a couple of exterior reviewers, as indicated by way of the referee record present in the court cases. there have been many extra appropriate papers than there has been area on hand within the symposium software, which made this system committee’s activity super di cult. eventually forty six papers have been chosen for presentation on the Symposium. as well as those contributed papers, the convention additionally incorporated invited displays via Dr. Jean-Daniel Boissonnat, INRIA Sophia-Antipolis, France and Professor Jin-Yi Cai, collage of Wisconsin at Madison, Wisconsin, united states. it truly is anticipated that almost all of the approved papers will look in a extra whole shape in scienti c journals.

Show description

Read Online or Download Algorithms and Computation: 11th International Conference, ISAAC 2000 Taipei, Taiwan, December 18–20, 2000 Proceedings PDF

Best algorithms books

The Nature of Code

How will we seize the unpredictable evolutionary and emergent houses of nature in software program? How can realizing the mathematical ideas in the back of our actual global aid us to create electronic worlds? This booklet specializes in various programming ideas and strategies in the back of machine simulations of usual platforms, from common strategies in arithmetic and physics to extra complex algorithms that allow subtle visible effects.

Creating New Medical Ontologies for Image Annotation: A Case Study

Developing New scientific Ontologies for snapshot Annotation specializes in the matter of the clinical photographs automated annotation strategy, that is solved in an unique demeanour by means of the authors. the entire steps of this method are defined intimately with algorithms, experiments and effects. the unique algorithms proposed by way of authors are in comparison with different effective comparable algorithms.

Algorithms and Models for the Web-Graph: 7th International Workshop, WAW 2010, Stanford, CA, USA, December 13-14, 2010. Proceedings

This publication constitutes the refereed court cases of the seventh foreign Workshop on Algorithms and versions for the Web-Graph, WAW 2010, held in Stanford, CA, united states, in December 2010, which was once co-located with the sixth foreign Workshop on web and community Economics (WINE 2010). The thirteen revised complete papers and the invited paper awarded have been conscientiously reviewed and chosen from 19 submissions.

Extra info for Algorithms and Computation: 11th International Conference, ISAAC 2000 Taipei, Taiwan, December 18–20, 2000 Proceedings

Example text

Ct , Strategies for Hotlink Assignments 27 3. si,1 , si,2 , . . , si,k , for i = 1, 2, . . , m, are m rows of vertices each row of size k. – The edge set E consists of the directed edges below: 1. (A0 , Ai ), and (Ai , Bi ), for all i = 1, . . , k − 1, 2. (Bi , Cj ), for all i = 1, . . , k − 1, and j = 1, 2, . . , t, 3. if si ∈ Cj then there exist directed edges (Cj , si,1 ), (Cj , si,2 ), . . , (Cj , si,k ). We can prove the following lemma. Lemma 1. There is a set cover of size at most k if and only if the directed graph G has a hotlink assignment which attains a gain of at least mk + 3k.

Section 5 gives a competitive ratio for RAND using a convexity argument based on the strategy framework. Section 6 concludes with a discussion of possible extensions to this work. 2 Related Work This section reviews previous results on competitive analysis for on-line replacement algorithms, both deterministic and randomized. We discuss criticisms of the common framework for competitive analysis that have been proposed in the literature. We conclude the section by observing that previous lower bounds involve request sequences with extremely low inherent miss rates, thus providing no information on many request sequences seen in practice that have moderate or high miss rates.

Analysis of the least-recently used algorithm LRU [23] likewise shows that LRUk is k-competitive, which is a trivial upper bound if β ≥ 1/k. The MARKINGk algorithm [11] is 2Hk -competitive, offering trivial upper bounds for β ≥ 1/2Hk ; and the PARTITIONk algorithm [21] and the EQUITABLEk algorithm [1] are Hk -competitive, providing trivial upper bounds for β ≥ 1/Hk . In comparison, our new analysis of RAND provides nontrivial upper bounds for all 0 < β < 1. In particular we show that RANDk is (1 − (1 − β)e−1/(1−β) )/βcompetitive on request sequences with inherent miss rate β.

Download PDF sample

Rated 4.93 of 5 – based on 15 votes