共查询到20条相似文献,搜索用时 15 毫秒
1.
During automated problem solving it may happen that some knowledge that is known at the user level is lost in the formal model. As this knowledge might be important for efficient problem solving, it seems useful to re-discover it in order to improve the efficiency of the solving procedure. This paper compares three methods for discovering certain implied constraints in the constraint models describing manufacturing (and other) processes with serial, parallel, and alternative operations. In particular, we focus on identifying equivalent nodes in the precedence graph with parallel and alternative branches. Equivalent nodes correspond to operations that either must be all simultaneously present or none of them can be present in the schedule. Such information is frequently known at the user level, but it is lost in the formal model. The paper shows that identifying equivalent nodes is an NP-hard problem in general, but it is tractable if the graph has a nested structure. As the nested structure is typical for real-life processes and workflows, we use the nested graphs to experimentally compare the proposed methods. 相似文献
2.
T. A. McKee 《Journal of Graph Theory》1983,7(2):177-181
The notions “series-parallel” and “nonseparable” are shown to be logical converses of each other when formulated in a particular dual-like fashion. Self-dual circuit/cutset characterizations are given of series-parallel and of series-parallel nonseparable graphs. 相似文献
3.
4.
M C Testik J K Cochran G C Runger 《The Journal of the Operational Research Society》2004,55(3):233-239
We study the short-term staffing problem of systems that experience random, non-stationary demand. The typical method to accommodate changes in arrival rate is to use historical data to identify peak periods and associated forecasting for upcoming time windows. In this paper, we develop a method that instead detects change as it happens. Motivated by an automatic call distributor system in a call centre with time-varying arrivals, we propose a change detection algorithm based upon non-homogeneous Poisson processes. The proposed method is general and may be thought of as a feed-forward strategy, in which we detect a change in the arrival process, estimate the new magnitude of the arrival rate, and assign an appropriate number of servers to the tasks. The generalized likelihood ratio statistic is used and a recommendation for its decision limit is developed. Simulation results are used to evaluate the performance of the detector in the context of a telephone call centre. 相似文献
5.
The max-cut problem asks for partitioning the nodes V of a graph G=(V,E) into two sets (one of which might be empty), such that the sum of weights of edges joining nodes in different partitions
is maximum. Whereas for general instances the max-cut problem is NP-hard, it is polynomially solvable for certain classes of graphs. For planar graphs, there exist several polynomial-time
methods determining maximum cuts for arbitrary choice of edge weights. Typically, the problem is solved by computing a minimum-weight
perfect matching in some associated graph. The most efficient known algorithms are those of Shih et al. (IEEE Trans. Comput.
39(5):694–697, 1990) and that of Berman et al. (WADS, Lecture Notes in Computer Science, vol. 1663, pp. 25–36, Springer, Berlin, 1999). The running time of the former can be bounded by
O(|V|\frac32log|V|)O(|V|^{\frac{3}{2}}\log|V|). The latter algorithm is more generally for determining T-joins in graphs. Although it has a slightly larger bound on the
running time of
O(|V|\frac32(log|V|)\frac32)a(|V|)O(|V|^{\frac{3}{2}}(\log|V|)^{\frac{3}{2}})\alpha(|V|), where α(|V|) is the inverse Ackermann function, it can solve large instances in practice. 相似文献
6.
G. S. Gasparian 《Combinatorica》1996,16(2):209-212
We provide a very short proof of the following theorem of Lovász, and of its consequences:A graph is perfect if and only if in every induced subgraph the number of vertices does not exceed the product of the stability and clique numbers of the subgraph.This proof is conceptually new: it does not use the replication operation, or any kind of polyhedral argument; the arguments resemble more the well-known ways of deducing structural properties of minimal imperfect graphs. However, the known proofs of these structural properties use Lovász's result, whereas the present work leads to a proof of Lovász's result itself, and actually to a slight sharpening.The author gratefully acknowledges financial support from Ministère de la Recherche et de la Technologie (the French Ministry of Research and Technology, MRT) which sponsored his three month visit to Laboratory ARTEMIS of Grenoble University which motivated him to do this work. 相似文献
7.
Ali Pourmiri 《Random Structures and Algorithms》2019,55(4):980-1009
We propose algorithms for allocating n sequential balls into n bins that are interconnected as a d‐regular n‐vertex graph G, where d ≥ 3 can be any integer. In general, the algorithms proceeds in n succeeding rounds. Let ? > 0 be an integer, which is given as an input to the algorithms. In each round, ball 1 ≤ t ≤ n picks a node of G uniformly at random and performs a nonbacktracking random walk of length ? from the chosen node and simultaneously collects the load information of a subset of the visited nodes. It then allocates itself to one of them with the minimum load (ties are broken uniformly at random). For graphs with sufficiently large girths, we obtain upper and lower bounds for the maximum number of balls at any bin after allocating all n balls in terms of ?, with high probability. 相似文献
8.
Rom Pinchasi 《Journal of Combinatorial Theory, Series A》2007,114(8):1363-1374
We introduce a new linear algebra approach for studying extremal problems in geometric graphs. We give alternative proofs to well-established facts on geometric graphs, as well as new results about triangulations. 相似文献
9.
The Pathmox approach for PLS path modeling: Discovering which constructs differentiate segments
下载免费PDF全文
![点击此处可从《商业与工业应用随机模型》网站下载免费的PDF全文](/ch/ext_images/free.gif)
The problem of heterogeneity represents a very important issue in the decision‐making process. Furthermore, it has become common practice in the context of marketing research to assume that different population parameters are possible depending on sociodemographic and psycho‐demographic variables such as age, gender, and social status. In recent decades, numerous approaches have been proposed with the aim of involving heterogeneity in the parameter estimation procedures. In partial least squares path modeling, the common practice consists of achieving a global measurement of the differences arising from heterogeneity. This leaves the analyst with the important task of detecting, a posteriori, which are the causal relationships (ie, path coefficients) that produce changes in the model. This is the case in Pathmox analysis, which solves the heterogeneity problem by building a binary tree to detect those segments of population that cause the heterogeneity. In this article, we propose extending the same Pathmox methodology to asses which particular endogenous equation of the structural model and which path coefficients are responsible of the difference. 相似文献
10.
Ladislav Nebeský 《Czechoslovak Mathematical Journal》2007,57(1):465-471
By a chordal graph is meant a graph with no induced cycle of length ⩾ 4. By a ternary system is meant an ordered pair (W, T), where W is a finite nonempty set, and T ⊆ W × W × W. Ternary systems satisfying certain axioms (A1)–(A5) are studied in this paper; note that these axioms can be formulated
in a language of the first-order logic. For every finite nonempty set W, a bijective mapping from the set of all connected chordal graphs G with V(G) = W onto the set of all ternary systems (W, T) satisfying the axioms (A1)–(A5) is found in this paper. 相似文献
11.
An algebraic analysis approach to linear time-varying systems 总被引:1,自引:0,他引:1
** Email: zerz{at}mathematik.uni-kl.de This paper introduces an algebraic analysis approach to lineartime-varying systems. The analysis is carried out in an almosteverywhere setting, i.e. the considered signals are smoothexcept for a set of measure zero, and the coefficients of thelinear ordinary differential equations are supposed to be rationalor meromorphic functions. The methodology is based on a normalform for matrices over the resulting ring of differential operators,which is a non-commutative analogue of the Smith form. Thisis used to establish a duality between linear time-varying systemson the one hand and modules over the ring of differential operatorson the other. This correspondence is based on the fact thatthe signal space is an injective cogenerator when consideredas a module over this ring of differential operators. 相似文献
12.
Models based on sparse graphs are of interest to many communities: they appear as basic models in combinatorics, probability theory, optimization, statistical physics, information theory, and more applied fields of social sciences and economics. Different notions of similarity (and hence convergence) of sparse graphs are of interest in different communities. In probability theory and combinatorics, the notion of Benjamini‐Schramm convergence, also known as left‐convergence, is used quite frequently. Statistical physicists are interested in the the existence of the thermodynamic limit of free energies, which leads naturally to the notion of right‐convergence. Combinatorial optimization problems naturally lead to so‐called partition convergence, which relates to the convergence of optimal values of a variety of constraint satisfaction problems. The relationship between these different notions of similarity and convergence is, however, poorly understood. In this paper we introduce a new notion of convergence of sparse graphs, which we call Large Deviations or LD‐convergence, and which is based on the theory of large deviations. The notion is introduced by “decorating” the nodes of the graph with random uniform i.i.d. weights and constructing corresponding random measures on and . A graph sequence is defined to be converging if the corresponding sequence of random measures satisfies the Large Deviations Principle with respect to the topology of weak convergence on bounded measures on . The corresponding large deviations rate function can be interpreted as the limit object of the sparse graph sequence. In particular, we can express the limiting free energies in terms of this limit object. We then establish that LD‐convergence implies the other three notions of convergence discussed above, and at the same time establish several previously unknown relationships between the other notions of convergence. In particular, we show that partition‐convergence does not imply left‐ or right‐convergence, and that right‐convergence does not imply partition‐convergence. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 51, 52–89, 2017 相似文献
13.
Patrice Perny Olivier Spanjaard Louis-Xavier Storme 《Annals of Operations Research》2006,147(1):317-341
This paper is devoted to the search of robust solutions in finite graphs when costs depend on scenarios. We first point out
similarities between robust optimization and multiobjective optimization. Then, we present axiomatic requirements for preference
compatibility with the intuitive idea of robustness in a multiple scenarios decision context. This leads us to propose the
Lorenz dominance rule as a basis for robustness analysis. Then, after presenting complexity results about the determination
of Lorenz optima, we show how the search can be embedded in algorithms designed to enumerate k best solutions. Then, we apply it in order to enumerate Lorenz optimal spanning trees and paths. We investigate possible
refinements of Lorenz dominance and we propose an axiomatic justification of OWA operators in this context. Finally, the results
of numerical experiments on randomly generated graphs are provided. They show the numerical efficiency of the suggested approach. 相似文献
14.
15.
Questions about a graph’s connected components are answered by studying appropriate powers of a special “adjacency matrix”
constructed with entries in a commutative algebra whose generators are idempotent. The approach is then applied to the Erd?s–Rényi
model of sequences of random graphs. Developed herein is a method of encoding the relevant information from graph processes
into a “second quantization” operator and using tools of quantum probability and infinite-dimensional analysis to derive formulas
that reveal the exact values of quantities that otherwise can only be approximated. In particular, the expected size of a
maximal connected component, the probability of existence of a component of particular size, and the expected number of spanning
trees in a random graph are obtained. 相似文献
16.
《Mathematical and Computer Modelling》1998,27(9-11):323-334
A dynamic model based on the error back-propagation learning principle in neural network theory is proposed for estimating origin-destination flows from the road entering and exiting counts in a transportation network. The origin-destination flows in each short time interval are estimated through minimization of the squared errors between the predicted and observed exiting counts which are normalized using a logistic function. Two numerical experiments are conducted to evaluate the performance of the proposed model; one uses a typical four-way intersection, and the other one uses a real freeway section. Numerical results show that the back-propagation based model is capable of tracking the time variations of the origin-destination flows with a high stability. 相似文献
17.
We present a scheme to solve the Steiner problem in directed graphs using a heuristic method to obtain upper bounds and thek shortest arborescences algorithm to compute lower bounds. We propose to combine these ideas in an enumerative algorithm. Computational results are presented for both thek shortest arborescences algorithm and the heuristic method, including reduction tests for the problem.This work was partially supported by CNPq, FINEP, CAPES and IBM do Brasil. 相似文献
18.
The paper provides necessary and sufficient solvability conditions for the time-variant discrete four block Nehari problem in terms of the existence of the stabilizing solutions to two coupled Riccati equations. A parametrization of the class of all solutions is also given. The results are easily obtained from a signature condition — a generalized Popov Yakubovich type argument-imposed on an appropiate rational node. The present development may be seen as an alternative of the theory developed by Gohberg, Kaashoek and Woerdeman [15]. 相似文献
19.
The stability of linear systems with uncertain bounded time-varying delays (without any constraints on the delay derivatives) is analyzed. It is assumed that the system is stable for some known constant values of the delays (but may be unstable for zero delay values). The existing (Lyapunov-based) stability methods are restricted to the case of a single non-zero constant delay value, and lead to complicated and restrictive results. In the present note for the first time a stability criterion is derived in the general multiple delay case without any constraints on the delay derivative. The simple sufficient stability condition is given in terms of the system matrices and the lengths of the delay segments. Different from the existing frequency domain methods which usually apply the small gain theorem, the suggested approach is based on the direct application of the Laplace transform to the transformed system and on the bounding technique in L2. A numerical example illustrates the efficiency of the method. 相似文献