Edge ranking and searching in partial orders

We consider a problem of searching an element in a partially ordered set (poset). The goal is to find a search strategy which minimizes the number of comparisons. Ben-Asher, Farchi and Newman considered a special case where the partial order has the maximum element and the Hasse diagram is a tree (tree-like posets) and they gave an O(n⁴log³n)-time algorithm for finding an optimal search strategy for such a partial order. We show that this problem is equivalent to finding edge ranking of a simple tree corresponding to the Hasse diagram, which implies the existence of a linear-time algorithm for this problem.Then we study a more general problem, namely searching in any partial order with maximum element. We prove that such a generalization is hard, and we give an -approximate polynomial-time algorithm for this problem.     

Martingale and stationary solutions for stochastic Navier-Stokes equations

Summary We prove the existence of martingale solutions and of stationary solutions of stochastic Navier-Stokes equations under very general hypotheses on the diffusion term. The stationary martingale solutions yield the existence of invariant measures, when the transition semigroup is well defined. The results are obtained by a new method of compactness.     

Randomization helps to perform independent tasks reliably

This paper is about algorithms that schedule tasks to be performed in a distributed failure‐prone environment, when processors communicate by message‐passing, and when tasks are independent and of unit length. The processors work under synchrony and may fail by crashing. Failure patterns are imposed by adversaries. Linearly‐bounded adversaries may fail up to a constant fraction of the processors. Weakly‐adaptive adversaries have to select, prior to the start of an execution, a subset of processors to be failure‐prone, and then may fail only the selected processors, at arbitrary steps, in the course of the execution. Strongly adaptive adversaries have a total number of failures as the only restriction on failure patterns. The measures of complexity are work, measured as the available processor steps, and communication, measured as the number of point‐to‐point messages. A randomized algorithm is developed, that attains both ??(n log*n) expected work and ??(n log*n) expected communication, against weakly‐adaptive linearly‐bounded adversaries, in the case when the numbers of tasks and processors are both equal to n. This is in contrast with performance of algorithms against strongly‐adaptive linearly‐bounded adversaries, which has to be Ω(n log n/log log n) in terms of work. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

On the Strong Convergence of Subgradients of Convex Functions

In this paper, results on the strong convergence of subgradients of convex functions along a given direction are presented; that is, the relative compactness (with respect to the norm) of the union of subdifferentials of a convex function along a given direction is investigated.     

The Strong Convergence of Subgradients of Convex Functions Along Directions: Perspectives and Open Problems

In this note, some questions concerning the strong convergence of subgradients of convex functions along a given direction are recalled and posed. It is shown that some open problems in literature are linked to that of the existence of limits of subgradients from subdifferentials along a given segment.     

On first-order quasi-variational inequalities with integral terms

This paper deals with first-order quasi-variational inequalities with integral terms associated with impulsive and switching control of piecewise-deterministic processes. Two formulations of quasi-variational inequalities are studied, characteristic and viscosity, and the relations between them are discussed. As a tool we apply convex analysis methods.     

Easy and hard instances of arc ranking in directed graphs

In this paper we deal with the arc ranking problem of directed graphs. We give some classes of graphs for which the arc ranking problem is polynomially solvable. We prove that deciding whether , where G is an acyclic orientation of a 3-partite graph is an NP-complete problem. In this way we answer an open question stated by Kratochvil and Tuza in 1999.     

Concentration Dependence of Anti- and Pro-Oxidant Activity of Polyphenols as Evaluated with a Light-Emitting Fe2+-Egta-H2O2 System

Hydroxyl radical (^•OH) scavenging and the regeneration of Fe²⁺ may inhibit or enhance peroxidative damage induced by a Fenton system, respectively. Plant polyphenols reveal the afore-mentioned activities, and their cumulative net effect may determine anti- or pro-oxidant actions. We investigated the influence of 17 phenolics on ultra-weak photon emission (UPE) from a modified Fenton system (92.6 µmol/L Fe²⁺, 185.2 µmol/L EGTA (ethylene glycol-bis(β-aminoethyl-ether)-N,N,N′,N,-tetraacetic acid) and 2.6 mmol/L H₂O₂ pH = 7.4). A total of 8 compounds inhibited (antioxidant effect), and 5 enhanced (pro-oxidant effect) UPE at all studied concentrations (5 to 50 µmol/L). A total of 4 compounds altered their activity from pro- to antioxidant (or vice versa) along with increasing concentrations. A total of 3 the most active of those (ferulic acid, chlorogenic acid and cyanidin 3-O-glucoside; mean UPE enhancement by 63%, 5% and 445% at 5 µmol/L; mean UPE inhibition by 28%, 94% and 24% at 50 µmol/L, respectively) contained catechol or methoxyphenol structures that are associated with effective ^•OH scavenging and Fe²⁺ regeneration. Most likely, these structures can determine the bidirectional, concentration-dependent activity of some phenolics under stable in vitro conditions. This is because the concentrations of the studied compounds are close to those occurring in human fluids, and this phenomenon should be considered in the case of dietary supplementation with isolated phenolics.