1,720,963 research outputs found
Competitive evaluation of threshold functions in the priced information model
No full textCicalese F, Milanic M. Competitive evaluation of threshold functions in the priced information model. Annals of Operations Research. 2009;188(1):111-132
Graphs of Separability at Most Two: Structural Characterizations and Their Consequences
No full textGraphs of separability at most k are defined as graphs in which every two non-adjacent vertices are separated by a set of at most k other vertices. For k ∈ {0,1}, the only connected graphs of separability at most k are complete graphs and block graphs, respectively. For k ≥ 3, graphs of separability at most k form a rich class of graphs containing all graphs of maximum degree k. Graphs of separability at most 2 generalize complete graphs, cycles and trees. We prove several characterizations of graphs of separability at most 2 and examine some of their consequences
On the approximability and exact algorithms for vector domination and related problems in graphs
Full text linkWe consider two graph optimization problems called vector domination and total vector domination. In vector domination one seeks a small subset S of vertices of a graph such that any vertex outside S has a prescribed number of neighbors in S. In total vector domination, the requirement is extended to all vertices of the graph. We prove that these problems (and several variants thereof) cannot be approximated to within a factor of clnn, where c is a suitable constant and n is the number of the vertices, unless P=NP. We also show that two natural greedy strategies have approximation factors lnΔ+O(1), where Δ is the maximum degree of the input graph. We also provide exact polynomial time algorithms for several classes of graphs. Our results extend, improve, and unify several results previously known in the literature
Competitive Boolean Function Evaluation. Beyond Monotonicity and the Symmetric Case
No full textWe study the extremal competitive ratio of Boolean function evaluation. We provide the first non-trivial lower and upper bounds for classes of Boolean functions which are not included in the class of monotone Boolean functions. For the particular case of symmetric functions our bounds are matching and we exactly characterize the best possible competitiveness achievable by a deterministic algorithm. Our upper bound is obtained by a simple polynomial time algorithm
Hardness, Approximability, and Exact Algorithms for Vector Domination and Total Vector Domination in Graphs
No full textWe consider two graph optimization problems called vector domination and total vector domination. In vector domination one seeks a small subset S of vertices of a graph such that any vertex outside S has a prescribed number of neighbors in S. In total vector domination, the requirement is extended to all vertices of the graph. We prove that these problems cannot be approximated to within a factor of clogn, for suitable constants c, unless every problem in NP is solvable in slightly super-polynomial time. We also show that two natural greedy strategies have approximation factors O(logΔ(G)), where Δ(G) is the maximum degree of the graph G. We also provide exact polynomial time algorithms for several classes of graphs. Our results extend, improve, and unify several results previously known in the literature
A Better Bouncers Algorithm
No full textSuppose we have a set of materials - e.g., drugs or genes - some combinations of which react badly together. We can experiment to see whether subsets contain any bad combinations and we want to find a maximal subset that does not. This problem is equivalent to finding a maximal independent set (or minimal vertex cover) in a hypergraph using group tests on the vertices. Consider the simple greedy algorithm that adds vertices one by one; after adding each vertex, the algorithm tests whether the subset now contains any edges and, if so, removes that vertex and discards it. We call this the "bouncer's algorithm" because it is reminiscent of how order is maintained as patrons are admitted to some bars. If this algorithm processes the vertices according to a given total preference order, then its solution is the unique optimum with respect to that order. Our main contribution is another algorithm that produces the same solution but uses fewer tests when few vertices are discarded: if the bouncer's algorithm discards d of the n vertices in the hypergraph, then our algorithm uses at most d(⌈log2 n⌉+1)+1 tests. It follows that, given black-box access to a monotone Boolean formula on n variables, we can find a minimal satisfying truth assignment using at most d(⌈log 2 n⌉+1)+1 tests, where d is the number of variables set to true. We also prove some bounds for partially adaptive algorithms
Characterizations of minimal dominating sets and the well-dominated property in lexicographic product graphs
No full textA graph is said to be well-dominated if all its minimal dominating sets are
of the same size. The class of well-dominated graphs forms a subclass of the
well studied class of well-covered graphs. While the recognition problem for
the class of well-covered graphs is known to be co-NP-complete, the recognition
complexity of well-dominated graphs is open.
In this paper we introduce the notion of an irreducible dominating set, a
variant of dominating set generalizing both minimal dominating sets and minimal
total dominating sets. Based on this notion, we characterize the family of
minimal dominating sets in a lexicographic product of two graphs and derive a
characterization of the well-dominated lexicographic product graphs. As a side
result motivated by this study, we give a polynomially testable
characterization of well-dominated graphs with domination number two, and show,
more generally, that well-dominated graphs can be recognized in polynomial time
in any class of graphs with bounded domination number. Our results include a
characterization of dominating sets in lexicographic product graphs, which
generalizes the expression for the domination number of such graphs following
from works of Zhang et al. (2011) and of \v{S}umenjak et al. (2012)
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
- …
