1,721,121 research outputs found
Stereoscopic families of permutations, and their applications (Extended Abstract)
No full text) Uriel Feige Robert Krauthgamer y Abstract A stereoscopic family of permutations maps an m- dimensional mesh into several 1-dimensional lines, in a way that jointly preserves distance information. Specifically, consider any two points and denote their distance on the m-dimensional mesh by d. Then the distance between their images, on the line on which these images are closest together, is O(d m ). We initiate a systematic study of stereoscopic families of permutations. We show a construction of these families that involves the use of m + 1 images. We also show that under some additional restrictions (namely, adjacent points on the image lines originate at points which are not too far away on the mesh), three images are necessary in order to construct such a family for the 2-dimensional mesh. We present two applications for stereoscopic families of permutations. One application is an algorithm for routing on the mesh that guarantees delivery of each packet within a number of s..
Max-Min Greedy Matching
Get PDFA bipartite graph G(U,V;E) that admits a perfect matching is given. One player imposes a permutation pi over V, the other player imposes a permutation sigma over U. In the greedy matching algorithm, vertices of U arrive in order sigma and each vertex is matched to the highest (under pi) yet unmatched neighbor in V (or left unmatched, if all its neighbors are already matched). The obtained matching is maximal, thus matches at least a half of the vertices. The max-min greedy matching problem asks: suppose the first (max) player reveals pi, and the second (min) player responds with the worst possible sigma for pi, does there exist a permutation pi ensuring to match strictly more than a half of the vertices? Can such a permutation be computed in polynomial time?
The main result of this paper is an affirmative answer for these questions: we show that there exists a polytime algorithm to compute pi for which for every sigma at least rho > 0.51 fraction of the vertices of V are matched. We provide additional lower and upper bounds for special families of graphs, including regular and Hamiltonian graphs. Our solution solves an open problem regarding the welfare guarantees attainable by pricing in sequential markets with binary unit-demand valuations
Fault-Tolerant ST-Diameter Oracles
Get PDFWe study the problem of estimating the ST-diameter of a graph that is subject to a bounded number of edge failures. An f-edge fault-tolerant ST-diameter oracle (f-FDO-ST) is a data structure that preprocesses a given graph G, two sets of vertices S, T, and positive integer f. When queried with a set F of at most f edges, the oracle returns an estimate Db of the ST-diameter diam(G−F, S, T), the maximum distance between vertices in S and T in G− F. The oracle has stretch σ ≥ 1 if diam(G−F, S, T) ≤ Db ≤ σ diam(G−F, S, T). If S and T both contain all vertices, the data structure is called an f-edge fault-tolerant diameter oracle (f-FDO). An f-edge fault-tolerant distance sensitivity oracles (f-DSO) estimates the pairwise graph distances under up to f failures. We design new f-FDOs and f-FDO-STs by reducing their construction to that of all-pairs and single-source f-DSOs. We obtain several new tradeoffs between the size of the data structure, stretch guarantee, query and preprocessing times for diameter oracles by combining our black-box reductions with known results from the literature. We also provide an information-theoretic lower bound on the space requirement of approximate f-FDOs. We show that there exists a family of graphs for which any f-FDO with sensitivity f ≥ 2 and stretch less than 5/3 requires Ω(n3/2) bits of space, regardless of the query time
On Estimation Algorithms vs Approximation Algorithms
No full textIn a combinatorial optimization problem, when given an input
instance, one seeks a feasible solution that optimizes the value
of the objective function. Many combinatorial optimization
problems are NP-hard. A way of coping with NP-hardness is by
considering approximation algorithms. These algorithms run in
polynomial time, and their performance is measured by their
approximation ratio: the worst case ratio between the value of the
solution produced and the value of the (unknown) optimal solution.
In some cases the design of approximation algorithms includes a
nonconstructive component. As a result, the algorithms become
estimation algorithms rather than approximation algorithms: they
allow one to estimate the value of the optimal solution, without
actually producing a solution whose value is close to optimal.
We shall present a few such examples, and discuss some open
questions
How to Hide a Clique?
Get PDFIn the well known planted clique problem, a clique (or alternatively, an independent set) of size k is planted at random in an Erdos-Renyi random G(n, p) graph, and the goal is to design an algorithm that finds the maximum clique (or independent set) in the resulting graph. We introduce a variation on this problem, where instead of planting the clique at random, the clique is planted by an adversary who attempts to make it difficult to find the maximum clique in the resulting graph. We show that for the standard setting of the parameters of the problem, namely, a clique of size k = √n planted in a random G(n, 1/2) graph, the known polynomial time algorithms can be extended (in a non-trivial way) to work also in the adversarial setting. In contrast, we show that for other natural settings of the parameters, such as planting an independent set of size k = n/2 in a G(n, p) graph with p = n^{-1/2}, there is no polynomial time algorithm that finds an independent set of size k, unless NP has randomized polynomial time algorithms
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe 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
Get PDF“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
Get PDFWe 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
- …
