35,154 research outputs found
Approximate Selection with Unreliable Comparisons in Optimal Expected Time
Get PDFGiven n elements, an integer k ≤ n/2 and a parameter ε ≥ 1/n, we study the problem of selecting an element with rank in (k-nε, k+nε] using unreliable comparisons where the outcome of each comparison is incorrect independently with a constant error probability, and multiple comparisons between the same pair of elements are independent. In this fault model, the fundamental problems of finding the minimum, selecting the k-th smallest element and sorting have been shown to require Θ(n log 1/Q), Θ(n log k/Q) and Θ(n log n/Q) comparisons, respectively, to achieve success probability 1-Q [Uriel Feige et al., 1994]. Considering the increasing complexity of modern computing, it is of great interest to develop approximation algorithms that enable a trade-off between the solution quality and the number of comparisons. In particular, approximation algorithms would even be able to attain a sublinear number of comparisons. Very recently, Leucci and Liu [Stefano Leucci and Chih-Hung Liu, 2022] proved that the approximate minimum selection problem, which covers the case that k ≤ nε, requires expected Θ(ε^{-1} log 1/Q) comparisons, but the general case, i.e., for nε < k ≤ n/2, is still open.
We develop a randomized algorithm that performs expected O(k/n ε^{-2} log 1/Q) comparisons to achieve success probability at least 1-Q. For k = n ε, the number of comparisons is O(ε^{-1} log 1/Q), matching Leucci and Liu’s result [Stefano Leucci and Chih-Hung Liu, 2022], whereas for k = n/2 (i.e., approximating the median), the number of comparisons is O(ε^{-2} log 1/Q). We also prove that even in the absence of comparison faults, any randomized algorithm with success probability at least 1-Q performs expected Ω(min{n, k/n ε^{-2} log 1/Q}) comparisons. As long as n is large enough, i.e., when n = Ω(k/n ε^{-2} log 1/Q), our lower bound demonstrates the optimality of our algorithm, which covers the possible range of attaining a sublinear number of comparisons. Surprisingly, for constant Q, our algorithm performs expected O(k/n ε^{-2}) comparisons, matching the best possible approximation algorithm in the absence of computation faults. In contrast, for the exact selection problem, the expected number of comparisons is Θ(n log k) with faults versus Θ(n) without faults. Our results also indicate a clear distinction between approximating the minimum and approximating the k-th smallest element, which holds even for the high probability guarantee, e.g., if k = n/2, Q = 1/n and ε = n^{-α} for α ∈ (0, 1/2), the asymptotic difference is almost quadratic, i.e., Θ̃(n^α) versus Θ̃(n^{2α})
Replication Data for: A Structural Model for the Coevolution of Networks and Behavior
No full textHsieh, Chih-Sheng, König, Michael D., and Liu, Xiaodong, (2022) “A Structural Model for the Coevolution of Networks and Behavior.” Review of Economics and Statistics 104:2, 355–367
Microcavity top-emitting organic light-emitting devices integrated with microlens arrays: Simultaneous enhancement of quantum efficiency, cd/A efficiency, color performances, and image resolution
No full text
Shang han liu jing ding fa
No full text陳澈撰 ; [劉晚榮輯]. 經絡歌訣 / 汪昂, [劉晚榮輯]. 傷寒六經定法 / 舒詔著 ; [劉晚榮輯]Chen Che zhuan ; [Liu Wanrong ji]. Jing luo ge jue / Wang Ang, [Liu Wanrong ji]. Shang han liu jing ding fa / Shu Zhao zhu ; [Liu Wanrong ji
Liu Chih's "Shang Kao Chien-ssu"(上高監司)
No full textIn the "Yang-ch'un Po-hsueh" (陽春白雪), which is a collection of san-ch'u (散曲), a kind of popular songs of the Yuan dynasty, we find two long pieces composed by Liu Chih, which vividly depicts some aspects of the social unrest of his time. The author of the present article analyses the first of the two to date, and gives some biographical notes of Liu Chih
Microcavity Top-Emitting Organic Light-Emitting Devices Integrated with Diffusers for Simultaneous Enhancement of Efficiencies and Viewing Characteristics
No full textXinjiang (China), folk dancing of Uyghurs
No full textFolk-dance of UighursImage is part of research conducted by Chang Chih-Yi for the article: Land Utilization and Settlement Possibilities in Sinkiang
Author(s): Chang Chih-Yi
Source: Geographical Review, Vol. 39, No. 1 (Jan., 1949), pp. 57-75
Published by: American Geographical Society
Stable URL: http://www.jstor.org/stable/211157http://www.jstor.org/stable/211157Grayscal
On the Wei Chin Sheng Liu Hua Tsan by Ku K'ai-chih
Get PDFThe Biography of Ku K'ai-chih, contained in the fifth volume of the Li Tai Ming Hua Chi (Notes on Famous Artists of Respective Periods), states that he wrote the Wei Chin Ming Ch'ên Hua Tsan (Eulogies on Portraits of Eminent Persons of the Wei and Chin Dynasties) in which he discussed on the subject in great details, and that he also wrote the Lun Hua (Discussions on Painting) to explain how to copy old masterpieces; this Biography ends with a paragraph beginning with an introductory sentence: “K’ai-chih, in his Wei Chin Shêng Liu Hua Tsan, said as follows.” (Ming Ch'ên and Shêng Liu are the same in meaning.)
The Lun Hua and the Wei Chin Shêng Liu Hua Tsan mentioned here seem confused in appearance, for the former lists and criticizes ancient paintings while the latter discribes about the attitude of mind, the materials and the techniques required in copying old works. An attempt was therefore made to interchange
settle the apparent contradiction between their titles and their contents (KIMBARA, Shōgo: “Studies on Art Criticism in Ancient China). However, the Wei Ching Shêng Liu Hua Tsan by Ku K'ai-chih existed separately, and was different from what was quoted in the Li Tai Ming Hua Chi. Portions of this Hua Tsan are found quoted in annotations on the Shih Shuo Hsin Yü (a collection of Chinese annecdotes) and in annotations by Li Shan on the Wên Hsuan (a collection of old Chinese writings). Judged from these scattered segments, the original form of the Hua Tsan by Ku K'ai-chih appears to have been modelled after the Hua Tsan written by Ts'ao Chih in the Wei Dynasty: that is to say, it probably was a versified writing consisting of four-character lines preceded by an introductory paragraph. This is the real Wei Chin Shêng Liu Hua Tsan, or the Wei Chin Ming Chên Hua Tsan “in which he discussed in great details” according to the Li Tai Ming Hua Chi.
The discussions in the Wei Chin Shêng Liu Hua Tsan are not on the characteristics and value of the paintings as works of art, but are on the personalities of the figure subjects depicted therein. They are notes, not on the paintings themselves but on their subject matters. This was the case even with Ku K'aichih, who was an artist and art critic of a very creative mind. This fact may be understood to represent an aspect of the characteristic Chinese term of view on art.
The portion entitled Wei Chin Shêng Liu Hua Tsan in the Li Tai Ming Hua Chih is nothing but a part of the Lun Hua. It explains the mental and material preparations necessary in copying old paintings, while the portion entitled Lun Hua comments on the styles of old masters in order to tell what are important in copying their works. The two are parts of the same writing, Lun Hua, giving instructions for copyists. The present writer is inclined to think that a careless editor in a later period gave the title Wei Chin Shêng Liu Hua Tsan to the second half of what had been recorded as Lun Hua in the Li Tai Ming Hua Chi, simply because a mention of the Hua Tsan is found in a previous paragraph of the Biography.journal articl
- …
