1,721,060 research outputs found
Approximability of the Discrete Fréchet Distance
Full text linkThe Fréchet distance is a popular and widespread distance measure for point sequences and for curves. About two years ago, Agarwal et al [SIAM J. Comput. 2014] presented a new (mildly) subquadratic algorithm for the discrete version of the problem. This spawned a flurry of activity that has led to several new algorithms and lower bounds.
In this paper, we study the approximability of the discrete Fréchet distance. Building on a recent result by Bringmann [FOCS 2014], we present a new conditional lower bound that strongly subquadratic algorithms for the discrete Fréchet distance are unlikely to exist, even in the one-dimensional case and even if the solution may be approximated up to a factor of 1.399.
This raises the question of how well we can approximate the Fréchet distance (of two given d-dimensional point sequences of length n) in strongly subquadratic time. Previously, no general results were known. We present the first such algorithm by analysing the approximation ratio of a simple, linear-time greedy algorithm to be 2^Theta(n). Moreover, we design an alpha-approximation algorithm that runs in time O(n log n + n^2 / alpha), for any alpha in [1, n]. Hence, an n^epsilon-approximation of the Fréchet distance can be computed in strongly subquadratic time, for any epsilon > 0
Fine-Grained Complexity of Earth Mover’s Distance Under Translation
Full text linkPublisher Copyright: © Karl Bringmann, Frank Staals, Karol Węgrzycki, and Geert van Wordragen.The Earth Mover’s Distance is a popular similarity measure in several branches of computer science. It measures the minimum total edge length of a perfect matching between two point sets. The Earth Mover’s Distance under Translation (EMDuT) is a translation-invariant version thereof. It minimizes the Earth Mover’s Distance over all translations of one point set. For EMDuT in R1, we present an Oe(n2)-time algorithm. We also show that this algorithm is nearly optimal by presenting a matching conditional lower bound based on the Orthogonal Vectors Hypothesis. For EMDuT in Rd, we present an Oe(n2d+2)-time algorithm for the L1 and L∞ metric. We show that this dependence on d is asymptotically tight, as an no(d)-time algorithm for L1 or L∞ would contradict the Exponential Time Hypothesis (ETH). Prior to our work, only approximation algorithms were known for these problems.Peer reviewe
Efficient optimization of many objectives by approximation-guided evolution
No full textAbstract not availableMarkus Wagner, Karl Bringmann, Tobias Friedrich, Frank Neuman
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Full text linkWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
Fine-Grained Complexity Theory (Tutorial)
No full textSuppose the fastest algorithm that we can design for some problem runs in time O(n^2). However, we want to solve the problem on big data inputs, for which quadratic time is impractically slow. We can keep searching for a faster algorithm, but maybe none exists. Is there any reasoning that provides evidence against significantly faster algorithms, and thus allows us to stop searching? In other words, is there an analogue of NP-hardness for polynomial-time problems?
In this tutorial, we will give an introduction to fine-grained complexity theory, which allows to rule out faster algorithms by proving conditional lower bounds via fine-grained reductions from certain key conjectures. We will define these terms and show exemplary lower bounds
The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds
No full textWe pose the fine-grained hardness hypothesis that the textbook algorithm forthe NFA Acceptance problem is optimal up to subpolynomial factors, even fordense NFAs and fixed alphabets. We show that this barrier appears in many variations throughout thealgorithmic literature by introducing a framework of Colored Walk problems.These yield fine-grained equivalent formulations of the NFA Acceptance problemas problems concerning detection of an --walk with a prescribed colorsequence in a given edge- or node-colored graph. For NFA Acceptance on sparseNFAs (or equivalently, Colored Walk in sparse graphs), a tight lower boundunder the Strong Exponential Time Hypothesis has been rediscovered severaltimes in recent years. We show that our hardness hypothesis, which concernsdense NFAs, has several interesting implications: - It gives a tight lower bound for Context-Free Language Reachability. Thisproves conditional optimality for the class of 2NPDA-complete problems,explaining the cubic bottleneck of interprocedural program analysis. - It gives a tight lower bound for the Word Breakproblem on strings of length and dictionaries of total size . - It implies the popular OMv hypothesis. Since the NFA acceptance problem isa static (i.e., non-dynamic) problem, this provides a static reason for thehardness of many dynamic problems. Thus, a proof of the NFA Acceptance hypothesis would resolve severalinteresting barriers. Conversely, a refutation of the NFA Acceptance hypothesismay lead the way to attacking the current barriers observed for Context-FreeLanguage Reachability, the Word Break problem and the growing list of dynamicproblems proven hard under the OMv hypothesis.Comment: 35 pages, TheoretiCS journal versio
- …
