Discovering implied constraints in precedence graphs with alternatives

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.     

Series-parallel graphs: A logical approach

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.     

Adaptive server staffing in the presence of time-varying arrivals: a feed-forward control approach

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.     

Partitioning planar graphs: a?fast combinatorial approach for max-cut

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.     

Minimal imperfect graphs: A simple approach

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.     

Balanced allocation on graphs: A random walk approach

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.     

Linear algebra approach to geometric graphs

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.     

The Pathmox approach for PLS path modeling: Discovering which constructs differentiate segments

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.     

A new approach to chordal graphs

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.     

An algebraic analysis approach to linear time-varying systems

^** 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.     

Convergent sequences of sparse graphs: A large deviations approach

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     

A decision-theoretic approach to robust optimization in multivalued graphs

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.     

Connected components and evolution of random graphs: an algebraic approach

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.     

Estimation of time-varying origin-destination flows from traffic counts: A neural network approach

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.     

An approach for the Steiner problem in directed graphs

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 CNP_q, FINEP, CAPES and IBM do Brasil.     

The time-varying discrete four block Nehari problem: A generalized Popov-Yakubovich type approach

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

Stability of linear systems with time-varying delays: A direct frequency domain approach

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$L_2$. A numerical example illustrates the efficiency of the method.