1,721,087 research outputs found
Efficient Truthful Mechanisms for the Single-Source Shortest Paths Tree Problem
No full textLet a communication network be modelled by an undirected graph G=(V,E) of n nodes and m edges, and assume that each edge is controlled by a selfish agent. In this paper we analyze the problem of designing a truthful mechanism for computing one of the most used structures in communication networks, i.e., the single-source shortest paths tree. More precisely, we will show that under various realistic agents’ behavior scenarios, it can be guaranteed not only the existence, but also the efficiency (in terms of running time complexity) of such mechanisms. In particular, for the fundamental case in which the problem is utilitarian, we will show that a truthful mechanism can be computed in O(mn log α(m,n)) time, where α(m,n) is the classic inverse of the Ackermann’s function
A Truthful (2-2/k)-Approximation Mechanism for the Steiner Tree Problem with k Terminals
No full textLet a communication network be modelled by an undirected graph G = ( V, E) of n nodes and m edges, and assume that each edge is owned by a selfish agent, which establishes the cost of using her edge by pursuing only her personal utility. In such a non-cooperative setting, we aim at designing a truthful mechanism for the problem of finding a minimum Steiner tree of G. Since no poly-time computable exact truthful mechanism can exist for such a problem (unless P=NP), we provide a truthful (2 - 2/k)-approximation mechanism which can be computed in O((n + k2)m log α(m, n)) time, where k is the number of terminal nodes, and α(.,.) is the classic inverse of the Ackermann's function. This compares favorably with the previous known O(kn(m + n log n)) time and 2-approximate truthful mechanism for solving the problem
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
Multiple-Edge-Fault-Tolerant Approximate Shortest-Path Trees
No full textLet G be an n-node and m-edge positively real-weighted undirected graph. For any given integer f≥ 1 , we study the problem of designing a sparse f-edge-fault-tolerant (f-EFT) σ-approximate single-source shortest-path tree (σ-ASPT), namely a subgraph of G having as few edges as possible and which, following the failure of a set F of at most f edges in G, contains paths from a fixed source that are stretched by a factor of at most σ. To this respect, we provide an algorithm that efficiently computes an f-EFT (2 | F| + 1) -ASPT of size O(fn). Our structure improves on a previous related construction designed for unweighted graphs, having the same size but guaranteeing a larger stretch factor of 3 (f+ 1) , plus an additive term of (f+ 1) log n. Then, we show how to convert our structure into an efficient f-EFT single-source distance oracle, that can be built in O(fmα(m,n)+fnlog3n) time, has size O(fnlog 2n) , and in O(| F| 2log 2n) time is able to report a (2 | F| + 1) -approximate distance from the source to any node in G- F. Moreover, our oracle can return a corresponding approximate path in the same amount of time plus the path’s size. The oracle is obtained by tackling another fundamental problem, namely that of updating a minimum spanning forest (MSF) of G following a batch of k simultaneous modification (i.e., edge insertions, deletions and weight changes). For this problem, we build in O(mlog 3n) time an oracle of size O(mlog 2n) , that reports in O(k2log 2n) time the (at most 2k) edges either exiting from or entering into the MSF. Finally, for any integer k≥ 1 , we complement all our results with a lower bound of Ω(n1+1k) to the size of any f-EFT σ-ASPT with f≥ log n and σ<3k+1k+1, that holds if the Erdős’ girth conjecture is true
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
Exact and Approximate Truthful Mechanisms for the Shortest Paths Tree Problem
No full textLet a communication network be modeled by an undirected graph G=(V,E) of n nodes and m edges, and assume that edges are controlled by selfish agents. In this paper we analyze the problem of designing a truthful mechanism for computing one of the most popular structures in communication networks, i.e., the single-source shortest paths tree.
More precisely, we will study several realistic scenarios, in which each agent can own either a single or multiple edges of G. In particular, for the single-edge case, we will show that: (i) in the classic utilitarian case, the problem can be solved efficiently in O(mnlogα(m,n)) time, where ±(m,n) is the inverse of the Ackermanns function; (ii) in a meaningful non-utilitarian case, namely that in which agents valuation functions only depend on the edge lengths, the problem can be solved in O(m+nlogn) time. Conversely, for the multiple-edges case, we will show in the utilitarian case an O(mP+nPlogn) time truthful mechanism, where P=O(n) denotes the number of agents participating in the solution, while in the same non-utilitarian case we will prove a general lower bound to the approximation ratio that can be achieved by any truthful mechanism, by showing that no c-approximate mechanism can exist, for any fixed c < 5+√13 / 3+√13
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
- …
