Precoloring Extension of Co-Meyniel Graphs

The pre-coloring extension problem consists, given a graph G and a set of nodes to which some colors are already assigned, in finding a coloring of G with the minimum number of colors which respects the pre-coloring assignment. This can be reduced to the usual coloring problem on a certain contracted graph. We prove that pre-coloring extension is polynomial for complements of Meyniel graphs. We answer a question of Hujter and Tuza by showing that “PrExt perfect” graphs are exactly the co-Meyniel graphs, which also generalizes results of Hujter and Tuza and of Hertz. Moreover we show that, given a co-Meyniel graph, the corresponding contracted graph belongs to a restricted class of perfect graphs (“co-Artemis” graphs, which are “co-perfectly contractile” graphs), whose perfectness is easier to establish than the strong perfect graph theorem. However, the polynomiality of our algorithm still depends on the ellipsoid method for coloring perfect graphs. C.N.R.S. Final version received: January, 2007     

The Concavity Assumption on Felicities and Asymptotic Dynamics in the RSS Model

An analysis of the RSS model in mathematical economics involves the study of an infinite-horizon variational problem in discrete time. Under the assumption that the felicity function is upper semicontinuous and “supported” at the value of the maximally-sustainable level of a production good, we report a generalization of results on the equivalence, existence and asymptotic convergence of optimal trajectories in this model. We consider two parametric specifications, and under the second, identify a “symmetry” condition on the zeroes of a “discrepancy function” underlying the objective function that proves to be necessary and sufficient for the asymptotic convergence of good programs. With a concave objective function, as is standard in the antecedent literature, we show that the symmetry condition reduces to an equivalent “non-interiority” condition.     

Solving large set covering problems for crew scheduling

This paper presents a computationally effective heuristic method which produces good-quality solutions for large-scale set covering problems with thousands of constraints and about one million variables. The need to solve such large-scale problems arises from a crew scheduling problem of mass transit agencies where the number of work shifts required has to be minimized. This problem may be formulated as a large-scale non-unicost set covering problem whose rows are trips to be performed while columns stand for round trips. The proposed method is mainly based on lagragian relaxation and sub-gradient optimization. After the reduction of the number of rows and columns by the logical tests, “greedy” heuristic algorithms provide upper and lower bounds which are continuously improved to produce goodquality solutions. Computational results, regarding randomly generated problems and real life problems concerning crew scheduling at Italian Railways Company, show that good-quality solutions can be obtained at an acceptable computational cost. This work was supported by the project “Progetto Finalizzato Transporti 2” of National Research Council of Italy (C.N.R.) contract No. 94.01436PF74 and by “Ferrovie dello Stato S.p.A.”     

Formal asymptotics of eigenmodes for oscillating elastic spatial bodies with concentrated masses

Limit spectral problems are derived for the problem on oscillations of a solid with small heavy (or light) inclusions. The asymptotic ansatzs for eigenvalues and eigenvectors, as well as the limit problems, are crucially dependent on both the relation between the geometric and physical parameters and the disposition of the inclusions. It is established that, for heavy inclusions, the limit problems are united into a more complex resultant problem describing the “far action” in the set of inclusions. Bibliography: 39 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 342, 2007, pp. 31–76.     

Asymptotics of the optimal time in a singular perturbed linear time-optimal problem

We consider an abstract attainability problem under constraints of asymptotic character and describe a general approach to constructing “nonsequential” attraction sets in the space of generalized elements formalized as finitely additive measures. We also study the existence and structure of an asymptotic formula universal in the range of “asymptotic constraints” and topologies of the space of generalized elements in the case when the space of ordinary solutions is not necessarily compactifiable.     

An algebraic foundation for factoring linear boundary problems

Motivated by boundary problems for linear differential equations, we define an abstract boundary problem as a pair consisting of a surjective linear map (“differential operator”) and an orthogonally closed subspace of the dual space (“boundary conditions”). Defining the composition of boundary problems corresponding to their Green’s operators in reverse order, we characterize and construct all factorizations of a boundary problem from a given factorization of the defining operator. For the case of ordinary differential equations, the main results can be made algorithmic. We conclude with a factorization of a boundary problem for the wave equation. This work was supported by the Austrian Science Fund (FWF) under the SFB grant F1322.     

Exploring the complexity boundary between coloring and?list-coloring

Many classes of graphs where the vertex coloring problem is polynomially solvable are known, the most prominent being the class of perfect graphs. However, the list-coloring problem is NP-complete for many subclasses of perfect graphs. In this work we explore the complexity boundary between vertex coloring and list-coloring on such subclasses of perfect graphs where the former admits polynomial-time algorithms but the latter is NP-complete. Our goal is to analyze the computational complexity of coloring problems lying “between” (from a computational complexity viewpoint) these two problems: precoloring extension, μ-coloring, and (γ,μ)-coloring. Flavia Bonomo partially supported by UBACyT Grants X606 and X069 (Argentina), and CNPq under PROSUL project Proc. 490333/2004-4 (Brazil). Guillermo Durán partially supported by FONDECyT Grant 1080286 and Millennium Science Institute “Complex Engineering Systems” (Chile), and CNPq under PROSUL project Proc. 490333/2004-4 (Brazil). Javier Marenco partially supported by UBACyT Grant X069 (Argentina), and CNPq under PROSUL project Proc. 490333/2004-4 (Brazil).     

Ploucquet’s “Refutation” of the Traditional Square of Opposition

In the 18th century, Gottfried Ploucquet developed a new syllogistic logic where the categorical forms are interpreted as set-theoretical identities, or diversities, between the full extension, or a non-empty part of the extension, of the subject and the predicate. With the help of two operators ‘O’ (for “Omne”) and ‘Q’ (for “Quoddam”), the UA and PA are represented as ‘O(S) – Q(P)’ and ‘Q(S) – Q(P)’, respectively, while UN and PN take the form ‘O(S) > O(P)’ and ‘Q(S) > O(P)’, where ‘>’ denotes set-theoretical disjointness. The use of the symmetric operators ‘–’ and ‘>’ gave rise to a new conception of conversion which in turn lead Ploucquet to consider also the unorthodox propositions O(S) – O(P), Q(S) – O(P), O(S) > Q(P), and Q(S) > Q(P). Although Ploucquet’s critique of the traditional theory of opposition turns out to be mistaken, his theory of the “Quantification of the Predicate” is basically sound and involves an interesting “Double Square of Opposition”. My thanks are due to Hanno von Wulfen for helpful discussions and for transforming the word-document into a Latex-file.     

Spatio-temporal symmetries and bifurcations via bi-orthogonal decompositions

Summary A tool for analyzing spatio-temporal complex physical phenomena was recently proposed by the authors, Aubry et al. [5]. This tool consists in decomposing a spatially and temporally evolving signal into orthogonal temporal modes (temporal “structures”) and orthogonal spatial modes (spatial “structures”) which are coupled. This allows the introduction of a temporal configuration space and a spatial one which are related to each other by an isomorphism. In this paper, we show how such a tool can be used to analyze space-time bifurcations, that is, qualitative changes in both space and time as a parameter varies. The Hopf bifurcation and various spatio-temporal symmetry related bifurcations, such as bifurcations to traveling waves, are studied in detail. In particular, it is shown that symmetry-breaking bifurcations can be detected by analyzing the temporal and spatial eigenspaces of the decomposition which then lose their degeneracy, namely their invariance under the symmetry. Furthermore, we show how an extension of the theory to “quasi-symmetries” permits the treatment of nondegenerate signals and leads to an exponentially decreasing law of the energy spectrum. Examples extracted from numerically obtained solutions of the Kuramoto-Sivashinsky equation, a coupled map lattice, and fully developed turbulence are given to illustrate the theory.     

On the concept of decision aiding process: an operational perspective

The paper presents the concept of decision aiding process as an extension of the decision process. The aim of the paper is to analyse the type of activities occurring between a “client” and an “analyst” both engaged in a decision process. The decision aiding process is analysed both under a cognitive point of view and an operational point of view: i.e. considering the “products”, or cognitive artifacts the process will deliver at the end. Finally the decision aiding process is considered as a reasoning process for which the update and revision problems hold.     

Asymptotic behavior of solutions to problems of elasticity theory at infinity in flat parabolic domains

Asymptotic representations of solutions to the boundary-value problems of elasticity theory are studied in domains with parabolic exit at infinity (or in bounded domains with singularities like polynomial zero sharpness). The procedure of derivating a formal asymptotic expansion looks like the algorithm of asymptotic analysis in domains. Under the Dirichlet conditions (displacements are prescribed on the boundary of a domain), it is not hard to justify the power asymptotic series. It follows from the theorem on the unique solvability of the problem in spaces of the type L₂ containing degrees of distance r=|x| as weight multipliers. For the Neumann conditions (stresses are prescribed on the boundary of a domain) an asymptotic expansion is justified by introducing the Eiry function Φ transforming the Lamé system to the biharmonic equation. Due to the appearance of the Dirichlet condition on Φ, the study of the asymptotic behavior of a solution to the last problem is simplified. The existence theorems and conditions for solvability of the “elastic” Neumann problem are presented. These results are based on the weighted Korn inequality. Bibliography: 29 titles. Translated fromProblemy Matematicheskogo Analiza. No. 15, 1995, pp. 162–200     

Prediction Error for Continuous-Time Stationary Processes with Singular Spectral Densities

The paper considers the mean square linear prediction problem for some classes of continuous-time stationary Gaussian processes with spectral densities possessing singularities. Specifically, we are interested in estimating the rate of decrease to zero of the relative prediction error of a future value of the process using the finite past, compared with the whole past, provided that the underlying process is nondeterministic and is “close” to white noise. We obtain explicit expressions and asymptotic formulae for relative prediction error in the cases where the spectral density possess either zeros (the underlying model is an anti-persistent process), or poles (the model is a long memory processes). Our approach to the problem is based on the Krein’s theory of continual analogs of orthogonal polynomials and the continual analogs of Szeg? theorem on Toeplitz determinants. A key fact is that the relative prediction error can be represented explicitly by means of the so-called “parameter function” which is a continual analog of the Verblunsky coefficients (or reflection parameters) associated with orthogonal polynomials on the unit circle. To this end first we discuss some properties of Krein’s functions, state continual analogs of Szeg? “weak” theorem, and obtain formulae for the resolvents and Fredholm determinants of the corresponding Wiener-Hopf truncated operators.     

The “walk in hemispheres” process and its applications to solving boundary value problems

Representations of solutions of boundary value problems for simple domains in the Monte Carlo algorithms are widely distributed [2]. In particular, widespread use is made of such a representation for the ball. It allows one to formally write an integral equation of the second kind for the required function in an arbitrary domain with regular boundary. Moreover, with the involvement of the joining conditions [1], one can picture a possible construction of a random process to “solve” the problem. However, the “walk in spheres” process, which solves the first boundary value problem for the Poisson equation, results in ɛ-biased estimators, and so the introduction of a regularization parameter is required. The authors investigate in detail the “walk in hemispheres” method, which has been proposed earlier by A. S. Sipin [10] without full justification. The use of the Green’s function for the hemisphere makes it possible to obtain estimators for the first and the third boundary value problems, as well as for the problem with discontinuous derivative; for a broad class of domains, these estimators are shown to be unbiased. The algorithms proposed feature a high degree of parallelism. Results of solving model problems are presented.     

Extensions of ordered semigroups

The present note summarizes the author's dissertation [2]. Let S and T be ordered semigroups, the latter with a zero element O. Let Σ be an ideal extension of S by T determined by a partial homomorphism ϕ of T^*=T/O into S. A partial solution is given to the problem of determining all ways of extending the given orders on S and T^* to Σ=S U T^*. Every such “extending order” (≤) on Σ carries with it a certain “null decomposition” T^*=X∪Y (X∩Y=ℴ) of T^*, and the existence and behavior of extending orders is discussed in terms of properties of null decompositions of T^*.     

A class of semi-linear equations of evolution

In this paper we prove existence, and study the asymptotic behavior of mild solutions of a class of semi-linear equations of evolution which are characterized by the fact that the associated homogeneous linear problem “generates” a strongly continuous semi-group of compact operators. We also prove a regularity result for which the associated homogeneous linear problem generates a holomorphic semi-group.     

The semantics of knowledge attributions

The basic idea of conversational contextualism is that knowledge attributions are context sensitive in that a given knowledge attribution may be true if made in one context but false if made in another, owing to differences in the attributors’ conversational contexts. Moreover, the context sensitivity involved is traced back to the context sensitivity of the word “know,” which, in turn, is commonly modelled on the case either of genuine indexicals such as “I” or “here” or of comparative adjectives such as “tall” or “rich.” But contextualism faces various problems. I argue that in order to solve these problems we need to look for another account of the context sensitivity involved in knowledge attributions and I sketch an alternative proposal.     

Convex programming with single separable constraint and bounded variables

In this paper a minimization problem with convex objective function subject to a separable convex inequality constraint “≤” and bounded variables (box constraints) is considered. We propose an iterative algorithm for solving this problem based on line search and convergence of this algorithm is proved. At each iteration, a separable convex programming problem with the same constraint set is solved using Karush-Kuhn-Tucker conditions. Convex minimization problems subject to linear equality/ linear inequality “≥” constraint and bounds on the variables are also considered. Numerical illustration is included in support of theory.     

Distribution results for lattices in SL(2,ℚ p )

In this paper we study the ergodic properties of the linear action of lattices Γ of SL(2,ℚ_p) on ℚ_p × ℚ_p and distribution results for orbits of Γ. Following Serre, one can define a “geodesic flow” for an associated tree (actually associated to GL(2,ℚ_p)). The approach we use is based on an extension of this approach to “frame flows” which are a natural compact group extension of the geodesic flow.     

The island confinement method for reducing search space in local search methods

Typically local search methods for solving constraint satisfaction problems such as GSAT, WalkSAT, DLM, and ESG treat the problem as an optimisation problem. Each constraint contributes part of a penalty function in assessing trial valuations. Local search examines the neighbours of the current valuation, using the penalty function to determine a “better” neighbour valuation to move to, until finally a solution which satisfies all the constraints is found. In this paper we investigate using some of the constraints as “hard” constraints, that are always satisfied by every trial valuation visited, rather than as part of a penalty function. In this way these constraints reduce the possible neighbours in each move and also the overall search space. The treating of some constraints as hard requires that the space of valuations that are satisfied is “connected” in order to guarantee that a solution can be found from any starting position within the region; thus the concept of islands and the name “island confinement method” arises. Treating some constraints as hard provides new difficulties for the search mechanism since the search space becomes more jagged, and there are more deep local minima. A new escape strategy is needed. To demonstrate the feasibility and generality of our approach, we show how the island confinement method can be incorporated in, and significantly improve, the search performance of two successful local search procedures, DLM and ESG, on SAT problems arising from binary CSPs. A preliminary version of this paper appeared in AAAI’2002.