Intersection properties of maximal directed cuts in digraphs

If $D$ is a finite digraph, a directed cut is a subset of arcs in $D$ having tail in some subset $X?V\left(D\right)$ and head in $V\left(D\right)?X$. In this paper we prove two general results concerning intersections between maximal paths, cycles and maximal directed cuts in $D$. As a direct consequence of these results, we deduce that there is a path, or a cycle, in $D$ that crosses each maximal directed cut.     

Index iteration theory for symplectic paths and multiple periodic solution orbits

In this paper, a survey on the index iteration theory for symplectic paths is given. Three applications of this theory are presented including closed characteristics on convex hypersurfaces and brake orbits on bounded domains.     

Redundant paths and reliability bounds in gamma networks

Multistage Interconnection Networks (MINs) are network systems providing fast and efficient communications at a reasonable cost. A gamma network is a specific class of MINs, which provides redundant paths in the system. In a gamma network, information from source nodes is transmitted through a specific set of routes to destination nodes. Reliability of an MIN is used as a measure of system’s ability to transform information from input to output devices. Due to the complexity of network configuration and availability of redundant paths, reliability bounds to estimate the exact reliability of a gamma network is proposed. A numerical example of an 8 × 8 gamma network is presented to demonstrate the accuracy of the reliability bounds. When the lower bound reliability provides sufficient assurance that the system will be operational at some specified time and closely approximates the exact reliability, then no further effort for obtaining the exact reliability expression is necessary.     

Shortest paths algorithms: Theory and experimental evaluation

We conduct an extensive computational study of shortest paths algorithms, including some very recent algorithms. We also suggest new algorithms motivated by the experimental results and prove interesting theoretical results suggested by the experimental data. Our computational study is based on several natural problem classes which identify strengths and weaknesses of various algorithms. These problem classes and algorithm implementations form an environment for testing the performance of shortest paths algorithms. The interaction between the experimental evaluation of algorithm behavior and the theoretical analysis of algorithm performance plays an important role in our research. This work was done while Boris V. Cherkassky was visiting Stanford University Computer Science Department and supported by the NSF and Powell Foundation grants mentioned below. Andrew V. Goldberg was supported in part by ONR Young Investigator Award N00014-91-J-1855, NSF Presidential Young Investigator Grant CCR-8858097 with matching funds from AT&T, DEC, and 3M, and a grant from Powell Foundation. Corresponding author. This work was done while Tomasz Radzik was a Postdoctoral Fellow at SORIE, Cornell University, and supported by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550, and by the Packard Fellowship of éva Tardos.     

Limiting behavior of weighted central paths in linear programming

We study the limiting behavior of the weighted central paths{(x(), s())} > 0 in linear programming at both = 0 and = . We establish the existence of a partition (B ,N ) of the index set { 1, ,n } such thatx _i() ands _j () as fori B , andj N , andx _N (),s _B () converge to weighted analytic centers of certain polytopes. For allk 1, we show that thekth order derivativesx ^(k) () ands ^(k) () converge when 0 and . Consequently, the derivatives of each order are bounded in the interval (0, ). We calculate the limiting derivatives explicitly, and establish the surprising result that all higher order derivatives (k 2) converge to zero when .     

Symmetry of cuts in fields of formal power series

The theory of cuts is an effective tool for studying ordered fields. We continue research into the relationship between the structure of cuts in a field of formal power series and algebraic properties of the field. __________ Translated from Algebra i Logika, Vol. 47, No. 2, pp. 174–185, March–April, 2008.     

Stochastic equivalence of ordered random variables with applications in reliability theory

This paper presents some conditions for stochastic equality of (univariate or multivariate) random variables under various stochastic orderings. The main results provide generalizations of several known results. Applications to stochastic equivalence and characterization problems associated with multivariate NBU (NBUE) distributions are also included.     

Domination game and minimal edge cuts

In this paper a relationship is established between the domination game and minimal edge cuts. It is proved that the game domination number of a connected graph can be bounded above in terms of the size of minimal edge cuts. In particular, if $C$ a minimum edge cut of a connected graph $G$, then ${\gamma }_g\left(G\right)\le {\gamma }_g(G?C)+2{\kappa }^{\prime }\left(G\right)$. Double-Staller graphs are introduced in order to show that this upper bound can be attained for graphs with a bridge. The obtained results are used to extend the family of known traceable graphs whose game domination numbers are at most one-half their order. Along the way two technical lemmas, which seem to be generally applicable for the study of the domination game, are proved.     

Oligopoly models for market price of electricity under demand uncertainty and unit reliability

Several oligopoly models have been proposed for representing strategic behavior in electricity markets, which include Bertrand, Cournot, and Supply Function Equilibrium (SFE). For the most part, these models are deterministic, with the exception of the SFE originally developed by Klemperer and Meyer. However, their model does not include supply side uncertainties. In this paper, we consider both load and supply side uncertainties (resulting from generator availabilities). We obtain Nash equilibrium solutions for Cournot and SFE models, in which asymmetric firms (whose generating units have different costs and capacities) submit their bids so that each firm’s expected profit is maximized.     

Pattern’s reliability importance under dependence condition and different information levels

Using martingale methods in reliability theory we developed the Barlow and Proschan reliability importance of a pattern to the system reliability under dependence conditions. We allowed several levels of information to calculate the importance measure.     

Improving reliability of a shared supplier with competition and spillovers

Supplier reliability is a key determinant of a manufacturer’s competitiveness. It reflects a supplier’s capability of order fulfillment, which can be measured by the percentage of order quantity delivered in a given time window. A perfectly reliable supplier delivers an amount equal to the order placed by its customer, while an unreliable supplier may deliver an amount less than the amount ordered. Therefore, when suppliers are unreliable, manufacturers often have incentives to help suppliers improve delivery reliability. Suppliers, however, often work with multiple manufacturers and the benefit of enhanced reliability may spill over to competing manufacturers. In this study, we explore how potential spillover influences manufacturers’ incentives to improve supplier’s reliability. We consider two manufacturers that compete with imperfectly substitutable products on Type I service level (i.e., in-stock probability). The manufacturers share a common supplier who, due to variations in production quality or yield, is unreliable. Manufacturers may exert efforts to improve the supplier’s reliability in the sense that the delivered quantity is stochastically larger after improvement. We develop a two-stage model that encompasses supplier improvement, uncertain supply and random demand in a competitive setting. In this complex model, we characterize the manufacturers’ equilibrium in-stock probability. Moreover, we characterize sufficient conditions for the existence of the equilibrium of the manufacturers’ improvement efforts. Finally, we numerically test the impact of market characteristics on the manufacturers’ equilibrium improvement efforts. We find that a manufacturer’s equilibrium improvement effort usually declines in market competition, market uncertainty or spillover effect, although its expected equilibrium profit typically increases in spillover effect.     

The analysis of evolutionary algorithms on sorting and shortest paths problems

The analysis of evolutionary algorithms is up to now limited to special classes of functions and fitness landscapes. E.g., it is not possible to characterize the set of TSP instances (or another NP-hard combinatorial optimization problem) which are solved by a generic evolutionary algorithm (EA) in an expected time bounded by some given polynomial. As a first step from artificial functions to typical problems from combinatorial optimization, we analyze simple EAs on well-known problems, namely sorting and shortest paths. Although it cannot be expected that EAs outperform the well-known problem specific algorithms on these simple problems, it is interesting to analyze how EAs work on these problems. The following results are obtained:– Sorting is the maximization of sortedness which is measured by one of several well-known measures of presortedness. The different measures of presortedness lead to fitness functions of quite different difficulty for EAs.– Shortest paths problems are hard for all types of EA, if they are considered as single-objective optimization problems, whereas they are easy as multi-objective optimization problems.     

The role of operating premises and reasoning paths in upper elementary students’ problem solving

The validity of students’ reasoning is central to problem solving. However, equally important are the operating premises from which students’ reason about problems. These premises are based on students’ interpretations of the problem information. This paper describes various premises that 11- and 12-year-old students derived from the information in a particular problem, and the way in which these premises formed part of their reasoning during a lesson. The teacher’s identification of differences in students’ premises for reasoning in this problem shifted the emphasis in a class discussion from the reconciliation of the various problem solutions and a focus on a sole correct reasoning path, to the identification of the students’ premises and the appropriateness of their various reasoning paths. Problem information that can be interpreted ambiguously creates rich mathematical opportunities because students are required to articulate their assumptions, and, thereby identify the origin of their reasoning, and to evaluate the assumptions and reasoning of their peers.     

A finitization of Littlewood's Tauberian theorem and an application in Tauberian remainder theory

In this paper we study Littlewood's Tauberian theorem from a proof theoretic perspective. We first use the Dialectica interpretation to produce an equivalent, finitary formulation of the theorem, and then carry out an analysis of Wielandt's proof to extract concrete witnessing terms. We argue that our finitization can be viewed as a generalized Tauberian remainder theorem, and we instantiate it to produce two concrete remainder theorems as a corollary, in terms of rates of convergence and rates metastability, respectively. We rederive the standard remainder estimate for Littlewood's theorem as a special case of the former.     

The reliability analysis of probabilistic and interval hybrid structural system

The aim of this paper is to evaluate the reliability of probabilistic and interval hybrid structural system. The hybrid structural system includes two kinds of uncertain parameters—probabilistic parameters and interval parameters. Based on the interval reliability model and probabilistic operation, a new probabilistic and interval hybrid reliability model is proposed. Firstly, we use the interval reliability model to analyze the performance function, and then sum up reliability of all regions divided by the failure plane. Based on the presented optimal criterion enumerating the main failure modes of hybrid structural system and the relationship of failure modes, the reliability of structure system can be obtained. By means of the numerical examples, the hybrid reliability model and the traditional probabilistic reliability model are critically contrasted. The results indicate the presented reliability model is more suitable for analysis and design of these structural systems and it can ensure the security of system well, and it only needs less uncertain information.     

On weights of induced paths and cycles in claw‐free and K1,r‐free graphs

Let G be a K_1,r ‐free graph (r ≥ 3) on n vertices. We prove that, for any induced path or induced cycle on k vertices in G (k ≥ 2r − 1 or k ≥ 2r, respectively), the degree sum of its vertices is at most (2r − 2)(n − α) where α is the independence number of G. As a corollary we obtain an upper bound on the length of a longest induced path and a longest induced cycle in a K_1,r ‐free graph. Stronger bounds are given in the special case of claw‐free graphs (i.e., r = 3). Sharpness examples are also presented. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 131–143, 2001     

Morse theory and conjugacy classes of finite subgroups

We construct a CAT(0) group containing a finitely presented subgroup with infinitely many conjugacy classes of finite-order elements. Unlike previous examples (which were based on right-angled Artin groups) our ambient CAT(0) group does not contain any rank 3 free abelian subgroups. We also construct examples of groups of type F _n inside mapping class groups, Aut(), and Out() which have infinitely many conjugacy classes of finite-order elements.      

A unified theory for coherent systems in reliability part III: Two special cases for multinary systems—binary-type coherence and homogeneous coherence

As shown in a companion-paper,¹ binary and multinary coherent systems can be studied with unified arguments, through monotone binary coherent systems. These are binary coherent systems submitted to some monotone constraint and generalize the classic theory of free binary coherent systems. By considering the unified point of view thus obtained, this paper gives what is perhaps the most suggestive representation for multinary coherent systems, since this extends the definition of binary coherent systems in terms of series-parallel (parallel-series) structures. Then, this paper examines the special case of multinary systems that can be studied directly with the classic theory of free binary coherent systems. It thus enlarges and complements, in a shorter unified manner, the particular cases considered in earlier studies.     

Classification of semispaces according to their types in infinite-dimensional vector spaces

It is shown that each semispaceC X naturally generates a relation of complete preorder onX with respect to which the pair (X C, C) is a cut ofX. By identifying the type of the semispace with the type of the cut generated by this semispace, the semispaces are classified according to their types. The obtained classification extends the classification of semispaces in finite-dimensional vector spaces due to Martinez-Legaz and Singer to infinite-dimensional spaces.Translated fromMatematicheskie Zametki, Vol. 64, No. 2, pp. 191–198, August, 1998.     

Problems and conjectures concerning connectivity, paths, trees and cycles in tournament-like digraphs

In this paper we collect a substantial number of challenging open problems and conjectures on connectivity, paths, trees and cycles in tournaments and classes of digraphs which contain tournaments as a subclass. The list is by no means exhaustive but is meant to show that the area has a large number of interesting open problems. We also mention problems for general digraphs when they are relevant in the context.