Approximation Algorithms for Union and Intersection Covering Problems [PDF]
, 2011 In a classical covering problem, we are given a set of requests that we need to satisfy (fully or partially), by buying a subset of items at minimum cost. For example, in the k-MST problem we want to find the cheapest tree spanning at least k nodes of an
Cygan, Marek +5 more
core +5 more sources
Top-k Querying of Unknown Values under Order Constraints [PDF]
, 2017 Many practical scenarios make it necessary to evaluate top-k queries over data items with partially unknown values. This paper considers a setting where the values are taken from a numerical domain, and where some partial order constraints are given over
Amarilli, Antoine +3 more
core +5 more sources
Semi-inclusive B Decays and Direct CP Violation in QCD Factorization [PDF]
, 2001 We have systematically investigated the semi-inclusive B decays B->MX, which are manifestations of the quark decay b->Mq, within the framework of QCD-improved factorization.
A. Ali +52 more
core +2 more sources
Ramsey-type graph coloring and diagonal non-computability [PDF]
, 2014 A function is diagonally non-computable (d.n.c.) if it diagonalizes against the universal partial computable function. D.n.c. functions play a central role in algorithmic randomness and reverse mathematics.
Patey, Ludovic
core +3 more sources
Solving Connectivity Problems Parameterized by Treedepth in Single-Exponential Time and Polynomial Space [PDF]
, 2020 A breakthrough result of Cygan et al. (FOCS 2011) showed that connectivity problems parameterized by treewidth can be solved much faster than the previously best known time ?^*(2^{?(twlog tw)}). Using their inspired Cut&Count technique, they obtained ?^*(
Hegerfeld, Falko, Kratsch, Stefan
core +2 more sources
Turbocharging Treewidth Heuristics [PDF]
, 2017 A widely used class of algorithms for computing tree decompositions of graphs are heuristics that compute an elimination order, i.e., a permutation of the vertex set. In this paper, we propose to turbocharge these heuristics.
Gaspers, Serge +2 more
core +1 more source
First draft genome assembly of the Argane tree (Argania spinosa) [PDF]
, 2018 Background: The Argane tree (Argania spinosa L. Skeels) is an endemic tree of southwestern Morocco that plays an important socioeconomic and ecologic role for a dense human population in an arid zone.
Abdelwahd, Rabha +33 more
core +1 more source
Negative density dependence and environmental heterogeneity effects on tree ferns across succession in a tropical montane forest. [PDF]
, 2014 Although tree ferns are an important component of temperate and tropical forests, very little is known about their ecology. Their peculiar biology (e.g., dispersal by spores and two-phase life cycle) makes it difficult to extrapolate current knowledge on
Chacón-Labella, Julia +4 more
core +3 more sources
Exploring $\pp$ scattering in the $\1N$ picture [PDF]
, 1995 In the large $N_c$ approximation to $QCD$, the leading $\pp$ scattering amplitude is expressed as the sum of an infinite number of tree diagrams. We investigate the possibility that an adequate approximation at energies up to somewhat more than one $GeV$
A. Salomone +36 more
core +3 more sources
Almost Every Simply Typed Lambda-Term Has a Long Beta-Reduction Sequence
, 2019 It is well known that the length of a beta-reduction sequence of a simply typed lambda-term of order k can be huge; it is as large as k-fold exponential in the size of the lambda-term in the worst case.
Asada, Kazuyuki +3 more
core +1 more source