Submodular set functions,matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the Rado-Edmonds theorem

For the problem maxlcub;Z(S): S is an independent set in the matroid Xrcub;, it is well-known that the greedy algorithm finds an optimal solution when Z is an additive set function (Rado-Edmonds theorem). Fisher, Nemhauser and Wolsey have shown that, when Z is a nondecreasing submodular set function satisfying Z(?)=0, the greedy algorithm finds a solution with value at least half the optimum value. In this paper we show that it finds a solution with value at least 1/(1 + α) times the optimum value, where α is a parameter which represents the ‘total curvature’ of Z. This parameter satisfies 0≤α≤1 and α=0 if and only if the set function Z is additive. Thus the theorems of Rado-Edmonds and Fisher-Nemhauser-Wolsey are both contained in the bound 1/(1 + α). We show that this bound is best possible in terms of α. Another bound which generalizes the Rado-Edmonds theorem is given in terms of a ‘greedy curvature’ of the set function. Unlike the first bound, this bound can prove the optimality of the greedy algorithm even in instances where Z is not additive. A third bound, in terms of the rank and the girth of X, unifies and generalizes the bounds (e?1)/e known for uniform matroids and $\text{1}\text{2}$ for general matroids. We also analyze the performance of the greedy algorithm when X is an independence system instead of a matroid. Then we derive two bounds, both tight: The first one is [1?(1?α/K)^k]/α where K and k are the sizes of the largest and smallest maximal independent sets in X respectively; the second one is 1/(p+α) where p is the minimum number of matroids that must be intersected to obtain X.     

Stable determination of an inhomogeneous inclusion by local boundary measurements

We deal with the problem of determining an inclusion within an electrostatic conductor from boundary measurements. Under mild a priori assumptions we establish optimal stability estimates. Measurements are performed on a portion of the boundary of the conductor.     

Genetic algorithms for supply-chain scheduling: A case study in the distribution of ready-mixed concrete

The coordination of just-in-time production and transportation in a network of partially independent facilities to guarantee timely delivery to distributed customers is one of the most challenging aspect of supply chain management. From a theoretical perspective, the timely production/distribution can be viewed as a hybrid combination of planning, scheduling and routing problems, each notoriously affected by nearly prohibitive combinatorial complexity. From a practical viewpoint, the problem calls for a trade-off between risks and profits. This paper focuses on the ready-mixed concrete delivery: in addition to the mentioned complexity, strict time-constraints forbid both earliness and lateness of the supply. After developing a detailed model of the considered problem, we propose a novel meta-heuristic approach based on a hybrid genetic algorithm combined with constructive heuristics. A detailed case study derived from industrial data is used to illustrate the potential of the proposed approach.     

The unsatisfiability threshold revisited

The problem of determining the unsatisfiability threshold for random 3-SAT formulas consists in determining the clause to variable ratio that marks the experimentally observed abrupt change from almost surely satisfiable formulas to almost surely unsatisfiable. Up to now, there have been rigorously established increasingly better lower and upper bounds to the actual threshold value. In this paper, we consider the problem of bounding the threshold value from above using methods that, we believe, are of interest on their own right. More specifically, we show how the method of local maximum satisfying truth assignments can be combined with results for the occupancy problem in schemes of random allocation of balls into bins in order to achieve an upper bound for the unsatisfiability threshold less than 4.571. In order to obtain this value, we establish a bound on the q-binomial coefficients (a generalization of the binomial coefficients). No such bound was previously known, despite the extensive literature on q-binomial coefficients. Finally, to prove our result we had to establish certain relations among the conditional probabilities of an event in various probabilistic models for random formulas. It turned out that these relations were considerably harder to prove than the corresponding ones for unconditional probabilities, which were previously known.     

Sliding mode control for a diffuse interface tumor growth model coupling a Cahn–Hilliard equation with a reaction–diffusion equation

We consider the sliding mode control (SMC) problem for a diffuse interface tumor growth model coupling a Cahn–Hilliard equation with a reaction–diffusion equation perturbed by a maximal monotone nonlinearity. We prove existence and regularity of strong solutions and, under further assumptions, a uniqueness result. Then, we show that the chosen SMC law forces the system to reach within finite time a sliding manifold that we chose in order that the tumor phase remains constant in time.     

Semigroups Generated by Ordinary Differential Operators in L 1(I)*

In this paper we give necessary and sufficient conditions for the existence of a C> ₀-semigroup in L ¹(I) (I real interval) generated by a second-order differential operator when suitable boundary conditions at the endpoints are imposed.     

Long-Time Behavior and Critical Limit of Subcritical SQG Equations in Scale-Invariant Sobolev Spaces

We consider the subcritical SQG equation in its natural scale-invariant Sobolev space and prove the existence of a global attractor of optimal regularity. The proof is based on a new energy estimate in Sobolev spaces to bootstrap the regularity to the optimal level, derived by means of nonlinear lower bounds on the fractional Laplacian. This estimate appears to be new in the literature and allows a sharp use of the subcritical nature of the \(L^\infty \) bounds for this problem. As a by-product, we obtain attractors for weak solutions as well. Moreover, we study the critical limit of the attractors and prove their stability and upper semicontinuity with respect to the strength of the diffusion.     

Bridging between short-range and long-range dependence with mixed spatio-temporal Ornstein–Uhlenbeck processes

While short-range dependence is widely assumed in the literature for its simplicity, long-range dependence is a feature that has been observed in data from finance, hydrology, geophysics and economics. In this paper, we extend a Lévy-driven spatio-temporal Ornstein–Uhlenbeck process by randomly varying its rate parameter to model both short-range and long-range dependence. This particular set-up allows for non-separable spatio-temporal correlations which are desirable for real applications, as well as flexible spatial covariances which arise from the shapes of influence regions. Theoretical properties such as spatio-temporal stationarity and second-order moments are established. An isotropic g-class is also used to illustrate how the memory of the process is related to the probability distribution of the rate parameter. We develop a simulation algorithm for the compound Poisson case which can be used to approximate other Lévy bases. The generalized method of moments is used for inference and simulation experiments are conducted with a view towards asymptotic properties.     

A multiplicity result for a class of nonlinear boundary value problems of the ambrosetti-prodi type

Summary In this paper we prove the existence of at least two solutions for a nonlinear elliptic boundary value problem of the Ambrosetti-Prodi type in the case when there exist two suitable supersolutions. This result follows from an abstract theorem of existence of multiple solutions which is a variant of a result due to Ambrosetti and Hess, [5].

---

Riassunto In questo lavoro si prova che per un problema al contorno del tipo Ambrosetti-Prodi esistono almeno due soluzioni se esistono due opportune soprasoluzioni. Tale risultato discende da un teorema astratto di esistenza di soluzioni multiple che é una variante di un risultato di Ambrosetti ed Hess, [5].

---

---

Paper written under the auspices of G.N.A.F.A., C.N.R., Italy.