共查询到20条相似文献,搜索用时 46 毫秒
1.
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 相似文献
2.
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. 相似文献
3.
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.” 相似文献
4.
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. 相似文献
5.
A. R. Danilin O. O. Kovrizhnykh 《Proceedings of the Steklov Institute of Mathematics》2010,271(1):53-68
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. 相似文献
6.
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. 相似文献
7.
8.
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). 相似文献
9.
Wolfgang Lenzen 《Logica Universalis》2008,2(1):43-58
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. 相似文献
10.
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. 相似文献
11.
Alexis Tsoukiàs 《Annals of Operations Research》2007,154(1):3-27
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. 相似文献
12.
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 L2 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 相似文献
13.
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. 相似文献
14.
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. 相似文献
15.
Extensions of ordered semigroups 总被引:3,自引:0,他引:3
Adam J. Hulin 《Semigroup Forum》1971,2(1):336-342
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*. 相似文献
16.
A. Pazy 《Israel Journal of Mathematics》1975,20(1):23-36
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. 相似文献
17.
Nikola Kompa 《Acta Analytica》2005,20(1):16-28
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. 相似文献
18.
Kalpana Dahiya Surjeet Kaur Suneja Vanita Verma 《Computational Optimization and Applications》2007,36(1):67-82
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. 相似文献
19.
François Ledrappier Mark Pollicott 《Bulletin of the Brazilian Mathematical Society》2005,36(2):143-176
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. 相似文献
20.
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. 相似文献