Search results for "Approx"

Scheduling stretched coupled-tasks with compatibilities constraints : model, complexity and approximation results for some class of graphs

2014

We tackle the makespan minimization coupled-tasks problem in presence of compatibility constraints. In particular, we focus on stretched coupled-tasks, {\it i.e.}coupled-tasks having the same sub-tasks execution time and idle time duration. We study severals problems in frame works of classic complexity and approximation for which the compatibility graph $G_c$ is bipartite (star, chain, $\ldots$) In such context, we design some efficient polynomial-time approximation algorithms according to difference parameters of the scheduling problem. When $G_c$ is a $k$-stage bipartite graph, we propose, among other, a $\frac{7}{6}$-approximation algorithm when $k=1$, and a $\frac{13}{9}$-approximation…

Theoretical Aspects of Scheduling Coupled-Tasks in the Presence of Compatibility Graph

2012

International audience; This paper presents a generalization of the coupled-task sche-duling problem introduced by Shapiro \cite{Shapiro}, where considered tasks are subject to incompatibility constraints depicted by an undirected graph. The motivation of this problem comes from data acquisition and processing in a mono-processor torpedo used for underwater exploration. As we add the compatibility graph, we focus on complexity of the problem, and more precisely on the boundary between $\mathcal{P}$ and $\mathcal{NP}$-completeness when some other input parameters are restricted (e.g. the ratio between the durations of the two sub-tasks composing a task): we adapt the global visualization of …

On a posteriori error bounds for approximations of the generalized Stokes problem generated by the Uzawa algorithm

2012

In this paper, we derive computable a posteriori error bounds for approximations computed by the Uzawa algorithm for the generalized Stokes problem. We show that for each Uzawa iteration both the velocity error and the pressure error are bounded from above by a constant multiplied by the L2-norm of the divergence of the velocity. The derivation of the estimates essentially uses a posteriori estimates of the functional type for the Stokes problem. peerReviewed

Analysis of errors caused by incomplete knowledge of material data in mathematical models of elastic media

2011

Reliable numerical solution of a class of nonlinear elliptic problems generated by the Poisson-Boltzmann equation

2020

We consider a class of nonlinear elliptic problems associated with models in biophysics, which are described by the Poisson-Boltzmann equation (PBE). We prove mathematical correctness of the problem, study a suitable class of approximations, and deduce guaranteed and fully computable bounds of approximation errors. The latter goal is achieved by means of the approach suggested in [S. Repin, A posteriori error estimation for variational problems with uniformly convex functionals. Math. Comp., 69:481-500, 2000] for convex variational problems. Moreover, we establish the error identity, which defines the error measure natural for the considered class of problems and show that it yields computa…

On the suffix automaton with mismatches

2007

International audience; In this paper we focus on the construction of the minimal deterministic finite automaton S_k that recognizes the set of suffixes of a word w up to k errors. We present an algorithm that makes use of S_k in order to accept in an efficient way the language of all suffixes of w up to k errors in every window of size r, where r is the value of the repetition index of w. Moreover, we give some experimental results on some well-known words, like prefixes of Fibonacci and Thue-Morse words, and we make a conjecture on the size of the suffix automaton with mismatches.

Nitrogen Adsorption on Graphene Sponges Synthesized by Annealing a Mixture of Nickel and Carbon Powders

2017

The present research has been supported by the National Research Programme for 2014–2017 “Multifunctional Materials and Composites, Photonics and Nanotechnologies”.

Microscopic calculation of the $\beta^-$ decays of $^{151}$Sm, $^{171}$Tm, and $^{210}$Pb with implications to detection of the cosmic neutrino backg…

2023

The electron spectral shapes corresponding to the low-$Q$ $\beta^-$-decay transitions $^{151}$Sm$(5/2^-_{\rm g.s.})\to\,^{151}\textrm{Eu}(5/2^+_{\rm g.s.})$, $^{151}$Sm$(5/2^-_{\rm g.s.})\to\,^{151}\textrm{Eu}(7/2^+_{1})$, $^{171}$Tm$(1/2^+_{\rm g.s.})\to\,^{171}\textrm{Yb}(1/2^-_{\rm g.s.})$, $^{171}$Tm$(1/2^+_{\rm g.s.})\to\,^{171}\textrm{Yb}(3/2^-_{1})$, $^{210}\textrm{Pb}(0^+_{\rm g.s.})\to\,^{210}\textrm{Bi}(1^-_{\rm g.s.})$, and $^{210}\textrm{Pb}(0^+_{\rm g.s.})\to\,^{210}\textrm{Bi}(0^-_{1})$ have been computed using beta-decay theory with several refinements for these first-forbidden nonunique (ff-nu) $\beta^-$ transitions. These ff-nu $\beta^-$ transitions have non-trivial electro…

On the origin and diversification of Podolian cattle breeds: testing scenarios of European colonization using genome-wide SNP data

2021

AbstractBackgroundDuring the Neolithic expansion, cattle accompanied humans and spread from their domestication centres to colonize the ancient world. In addition, European cattle occasionally intermingled with both indicine cattle and local aurochs resulting in an exclusive pattern of genetic diversity. Among the most ancient European cattle are breeds that belong to the so-called Podolian trunk, the history of which is still not well established. Here, we used genome-wide single nucleotide polymorphism (SNP) data on 806 individuals belonging to 36 breeds to reconstruct the origin and diversification of Podolian cattle and to provide a reliable scenario of the European colonization, throug…

Fusion of CNN and sparse representation for threat estimation near power lines and poles infrastructure using aerial stereo imagery

2021

Abstract Fires or electrical hazards and accidents can occur if vegetation is not controlled or cleared around overhead power lines, resulting in serious risks to people and property and significant costs to the community. There are numerous blackouts due to interfering the trees with the power transmission lines in hilly and urban areas. Power distribution companies are facing a challenge to monitor the vegetation to avoid blackouts and flash-over threats. Recently, several methods have been developed for vegetation monitoring; however, existing methods are either not accurate or could not provide better disparity map in the textureless region. Moreover, are not able to handle depth discon…