Irving van Heuven van Staereling,Bart de Keijzer,Guido Schäfer
Irving van Heuven van Staereling
We study the following natural variant of the budgeted maximum coverage problem: We are given a budget B and a hypergraph [Formula: see text], where each vertex has a non-negative cost and a non-negative profit. The goal is to select a set ...
Narad Rampersad,Jeffrey Shallit
Narad Rampersad
We show how to obtain, via a unified framework provided by logic and automata theory, many classical results of Brillhart and Morton on Rudin-Shapiro sums. The techniques also facilitate easy proofs for new results. ...
Alexey Milovanov
Alexey Milovanov
We combine Solomonoff's approach to universal prediction with algorithmic statistics and suggest to use the computable measure that provides the best "explanation" for the observed data (in the sense of algorithmic statistics) for predictio...
Michaël Cadilhac,Filip Mazowiecki,Charles Paperman et al.
Michaël Cadilhac et al.
We study the expressive power of polynomial recursive sequences, a nonlinear extension of the well-known class of linear recursive sequences. These sequences arise naturally in the study of nonlinear extensions of weighted automata, where (...
Faith Ellen,Rati Gelashvili,Philipp Woelfel et al.
Faith Ellen et al.
Many shared memory algorithms have to deal with the problem of determining whether the value of a shared object has changed in between two successive accesses of that object by a process when the responses from both are the same. Motivated ...
Characterizing Tractability of Simple Well-Designed Pattern Trees with Projection [0.03%]
带投影的简单良好设计模式树的可计算性特征研究
Stefan Mengel,Sebastian Skritek
Stefan Mengel
We study the complexity of evaluating well-designed pattern trees, a query language extending conjunctive queries with the possibility to define parts of the query to be optional. This possibility of optional parts is important for obtainin...
Eleni C Akrida,Leszek Gąsieniec,George B Mertzios et al.
Eleni C Akrida et al.
We study the design of small cost temporally connected graphs, under various constraints. We mainly consider undirected graphs of n vertices, where each edge has an associated set of discrete availability instances (labels). A journey from ...
Simone Bova,Friedrich Slivovsky
Simone Bova
We present new results on the size of OBDD representations of structurally characterized classes of CNF formulas. First, we prove that variable convex formulas (that is, formulas with incidence graphs that are convex with respect to the set...
Piotr Sankowski,Karol Węgrzycki
Piotr Sankowski
Consider an unweighted, directed graph G with the diameter D. In this paper, we introduce the framework for counting cycles and walks of given length in matrix multiplication time O ~ ( n ω ) . The framework is based on the fast deco...
Improved Distance Queries and Cycle Counting by Frobenius Normal Form [0.03%]
通过 Frobenius 标准形改进距离查询和计数
Piotr Sankowski,Karol Węgrzycki
Piotr Sankowski
Consider an unweighted, directed graph G with the diameter D. In this paper, we introduce the framework for counting cycles and walks of given length in matrix multiplication time O ~ ( n ω ) . The framework is based on the fast deco...