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     

Determination of reflector surfaces from near-field scattering data II. Numerical solution

Let be a nonisotropic point source of light, and the power intensity of this source in direction . Suppose that the light rays emitted by the source through an aperture fall on a perfectly reflecting surface and reflect off it so that the reflected rays illuminate a closed domain on some plane with intensity . The inverse problem consists of constructing the reflector surface from given position of the source , the input aperture , function , “target” set , and output intensity . For example, the input intensity may have a “bell”-like shape and we may wish to redistribute the energy uniformly over a prespecified region. The analytical formulation of the described above problem leads to a non-linear partial differential equation of Monge-Ampère type. In our previous paper we proved existence of weak solutions to this inverse problem and in this paper we describe and illustrate with examples an algorithm for its numerical solution. The proposed numerical method can be easily modified for the case when is a closed domain on an arbitrary surface. Received November 26, 1996     

An approach to matrix problems

A new general approach to the so-called “matrix problems” is given. With this approach, the “derivative” of a matrix problem is again a matrix problem of the same type.     

Homotopy classification of equivariant regular sections

In his paper [2], Bierstone proves the equivariant Gromov theorem which is an integrability theorem for “open regularity condition” of equivariant sections of a smooth G-fibre bundle under the assumption that all orbit bundles of base manifold are non-closed. Here, we prove the result without his assumption under a nice “open regularity condition” which we call “G-extensible”. One of the examples of “G-extensible condition” is given by notions of Thom-Boardman singularities.     

Some observations on repeated spring balance weighing designs

Summary Dey [3] has suggested a spring balance weighing design in preference to “repeated designs”, and later, Kulshreshtha and Dey [5] have suggested yet one more weighing design which, they say, would be preferred to “repeated designs” and to those suggested in [3], provided one is interested in estimating the weights of some of the objects with increased precision at the cost of precision for others. It has been shown here that, while the above findings may be true in some situations, one might, in a given problem, prefer “repeated designs” to those suggested in [3] and [5]. NSF Grant No. GP-28312 and GP-36562.     

A shape and topology optimization technique for solving a class of linear complementarity problems in function space

A shape and topology optimization driven solution technique for a class of linear complementarity problems (LCPs) in function space is considered. The main motivating application is given by obstacle problems. Based on the LCP together with its corresponding interface conditions on the boundary between the coincidence or active set and the inactive set, the original problem is reformulated as a shape optimization problem. The topological sensitivity of the new objective functional is used to estimate the “topology” of the active set. Then, for local correction purposes near the interface, a level set based shape sensitivity technique is employed. A numerical algorithm is devised, and a report on numerical test runs ends the paper.     

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.”     

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.     

A fuzzy closeness approach to fuzzy multi-attribute decision making

The aim of this paper is to develop a new fuzzy closeness (FC) methodology for multi-attribute decision making (MADM) in fuzzy environments, which is an important research field in decision science and operations research. The TOPSIS method based on an aggregating function representing “closeness to the ideal solution” is one of the well-known MADM methods. However, while the highest ranked alternative by the TOPSIS method is the best in terms of its ranking index, this does not mean that it is always the closest to the ideal solution. Furthermore, the TOPSIS method presumes crisp data while fuzziness is inherent in decision data and decision making processes, so that fuzzy ratings using linguistic variables are better suited for assessing decision alternatives. In this paper, a new FC method for MADM under fuzzy environments is developed by introducing a multi-attribute ranking index based on the particular measure of closeness to the ideal solution, which is developed from the fuzzy weighted Minkowski distance used as an aggregating function in a compromise programming method. The FC method of compromise ranking determines a compromise solution, providing a maximum “group utility” for the “majority” and a minimum individual regret for the “opponent”. A real example of a personnel selection problem is examined to demonstrate the implementation process of the method proposed in this paper.     

Junctions of singularly degenerating domains with different limit dimensions 1

The asymptotic series for solutions of the mixed boundary-value problem for the Poisson equation in a domain, which is a junction of singularly degenerating domains, are constructed. In this paper, which is the first part of the publication, the three-dimensional problem (“wheel hub with spokes”) and the analogous two-dimensional problems are considered. The methods of matched and compound asymptotic expansions are used. It is shown that a special self-adjoint extension of the operator of the limit problem in the “hub” supplied by the straight-line segments (“limits of spokes”) can be chosen as an asymptotical model of the problem in question; the extension parameters are to be some integral characteristics of the boundary-layer problems. Bibliography: 39 titles. Translated from Trudy Seminara imeni I. G. Petrovskogo. No. 18, pp. 3–78, 1995.     

On the problem of output feedback control synthesis under uncertainty and finite-time observers

We consider the problem of controlling a linear system of ordinary differential equations with a linear observable output. The system contains uncertain items (disturbances), for which we know only “hard” pointwise constraints. The problem of synthesizing a control that brings the trajectories of the system into a given target set in finite time is solved under weakened conditions without assuming that the control and the disturbance are of the same type. To this end, we suggest an approach that amounts to constructing an information set and a weakly invariant set with subsequent “aiming” of the first set at the second. Both stages are carried out in a finite-dimensional space, which permits one to use an efficient algorithm for solving the synthesis problem approximately on the basis of the ellipsoidal calculus technique. The results are illustrated by an example in which the control of a linear oscillation system is constructed.     

The return of the linear search problem

The linear search problem concerns a search on the real line for a point selected at random according to a given probability distribution. The search begins at zero and is made by a continuous motion with constant speed, first in one direction and then the other. The problem is to determine when it is possible to devise a “best” search plan. In former papers the best plan has been selected according to the criterion of minimum expected path length. In this paper we consider a more general, nonlinear criterion for a “best” plan and show that the substantive requirements of the earlier results are not affected by these changes.     

Orthogonal and bounded orthogonal spectral representations

The concept of an orthogonal spectral representation (OTSR) of a Hilbert spaceH relative to a spectral measureE(.) is introduced and it is shown that every Hilbert space admits an OTSR relative to a given spectral measure. Apart from the various results obtained about OTSRs, the principal result of Allan Brown (1974) is deduced as an easy consequence of this study. A new complete system of unitary invariants called the “equivalence of OTSRs”, is given for spectral measures. Two special types of OTSRs called “BOTSR” and “COBOTSR” are introduced and characterized respectively in terms of the “GCGS-property” and “CGS-property” of the associated spectral measure. Various complete systems of unitary invariants are given for spectral measures with the GCGS-property. Finally, the Wecken-Plesner-Rohlin theorem on hermitian operators with simple spectra is generalized to arbitrary spectral measures.     

Numerical simulation of sheath plasma by the particle method taking account of coulomb collisions

We study the problem of the behavior of a plasma bounded longitudinally by an absorbing sheath. This model contains charged particles (electrons and ions) moving subject to a self-consistent electrostatic field. New particle pairs are generated in the region of a distributed source. As a numerical model we used the electrostatic “particle-in-cell” method supplemented by the Emmert model for a bulk source and the algorithm of binary Coulomb collisions using the Monte Carlo method. We give a mathematical statement of the problem. The computations were carried out using the direct implicit method with the “explicit limit” time step. The results of numerical simulation of this system are given. We consider the formation and evoluiton of potential structures (multiple weak nonmonotonic double layers). Five figures. Bibliography: 35 titles. Translated fromProblemy Matematicheskoi Fiziki, 1998, pp. 75–89.     

KAM Stability for a three-body problem of the Solar system

A new (iso-energetic) KAM method is tested on a specific three-body problem “extracted” from the Solar system (Sun-Jupiter + asteroid 12 Victoria). Analytical results in agreement with the observed data are established. This paper is a concise presentation of [2]. Supported by the MIUR projects: “Dynamical Systems: Classical, Quantum, Stochastic” and “Variational Methods and Nonlinear Differential Equations” Received: February 3, 2004     

Analysis of the consistency of a mixed integer programming-based multi-category constrained discriminant model

Classification is concerned with the development of rules for the allocation of observations to groups, and is a fundamental problem in machine learning. Much of previous work on classification models investigates two-group discrimination. Multi-category classification is less-often considered due to the tendency of generalizations of two-group models to produce misclassification rates that are higher than desirable. Indeed, producing “good” two-group classification rules is a challenging task for some applications, and producing good multi-category rules is generally more difficult. Additionally, even when the “optimal” classification rule is known, inter-group misclassification rates may be higher than tolerable for a given classification model. We investigate properties of a mixed-integer programming based multi-category classification model that allows for the pre-specification of limits on inter-group misclassification rates. The mechanism by which the limits are satisfied is the use of a reserved judgment region, an artificial category into which observations are placed whose attributes do not sufficiently indicate membership to any particular group. The method is shown to be a consistent estimator of a classification rule with misclassification limits, and performance on simulated and real-world data is demonstrated.     

Direct problem of calculating the magnetic dipole field in a quasilayered medium

A method is developed for calculating the electromagnetic field of a magnetic dipole in a quasilayered two-dimensional medium. The quasi-three-dimensional problem is reduced to a two-dimensional problem for the Fourier-transformed electromagnetic field. An equivalent system of integral equations on the layer boundaries is obtained. This research was partially supported by the State Scientific-Technical Program “Future Information Technologies” (grant No. 0201.06.010) and the Interuniversity Scientific Program “Russian Universities: Basic Research.” Translated from Chislennye Metody v Matematicheskoi Fizike, Moscow State University, pp. 94–110, 1998.     

“Miniaturized” Linearizations for Quadratic 0/1 Problems

In order to solve a quadratic 0/1 problem, some techniques, consisting in deriving a linear integer formulation, are used. Those techniques, called “linearization”, usually involve a huge number of additional variables. As a consequence, the exact resolution of the linear model is, in general, very difficult. Our aim, in this paper, is to propose “economical” linear models. Starting from an existing linearization (typically the so-called “classical linearization”), we find a new linearization with fewer variables. The resulting model is called “Miniaturized” linearization. Based on this approach, we propose a new linearization scheme for which numerical tests have been performed.     

An Algebraic Approach to Physical Scales

This paper is aimed at introducing an algebraic model for physical scales and units of measurement. This goal is achieved by means of the concept of “positive space” and its rational powers. Positive spaces are “semi-vector spaces” on which the group of positive real numbers acts freely and transitively through the scalar multiplication. Their tensor multiplication with vector spaces yields “scaled spaces” that are suitable to describe spaces with physical dimensions mathematically. We also deal with scales regarded as fields over a given background (e.g., spacetime).     

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.