The discrete moment problem with fractional moments

Discrete moment problems (DMP) with integer moments were first introduced by Prékopa to provide sharp lower and upper bounds for functions of discrete random variables. Prékopa also developed fast and stable dual type linear programming methods for the numerical solutions of the problem. In this paper, we assume that some fractional moments are also available and propose basic theory and a solution method for the bounding problems. Numerical experiments show significant improvement in the tightness of the bounds.     

Graph transformations preserving the stability number

We analyse the relations between several graph transformations that were introduced to be used in procedures determining the stability number of a graph. We show that all these transformations can be decomposed into a sequence of edge deletions and twin deletions. We also show how some of these transformations are related to the notion of even pair introduced to color some classes of perfect graphs. Then, some properties of edge deletion and twin deletion are given and a conjecture is formulated about the class of graphs for which these transformations can be used to determine the stability number.     

Optimum departure times for commuters in congested networks

We propose an algorithm to compute the optimum departure time and path for a commuter in a congested network. Constant costs for use of arcs, cost functions of travel time depending on exogenous congestion and schedule delay are taken into account. A best path for a given departure time is computed with a previous algorithm for the generalized shortest path problem. The globally optimal departure time and an optimal path are determined by adapting Piyavskii's algorithm to the case of one-sided Lipschitz functions.This research has benefited from a grant of the Transportation Center of Northwestern University. The first author's research was partially supported by NSF grant No. SES-8911517 to Northwestern University. The second author's research was partially supported by AFOSR grants No. 89-0512 and 90-0008 to Rutgers University.     

Bimatroidal independence systems

An independence system Σ=(X, F) is called bimatroidal if there exist two matroidsM=(X F _M) andN=(X, F _N) such thatF=F _M∪ F_N. When this is the case, {M,N} is called a bimatroidal decomposition of Σ. This paper initiates the study of bimatroidal systems. Given the collection of circuits of an arbitrary independence system Σ (or, equivalently, the constraints of a set-covering problem), we address the following question: does Σ admit a bimatroidal decomposition {M,N} and, if so, how can we actually produce the circuits ofM andN? We derive a number of results concerning this problem, and we present a polynomial time algorithm to solve it when every two circuits of Σ have at most one common element. We also propose different polynomial time algorithms for set covering problems defined on the circuit-set of bimatroidal systems.     

Cause-effect relationships and partially defined Boolean functions

This paper investigates the use of Boolean techniques in a systematic study of cause-effect relationships. The model uses partially defined Boolean functions. Procedures are provided to extrapolate from limited observations, concise and meaningful theories to explain the effect under study, and to prevent (or provoke) its occurrence.     

On Edge Semi-Isomorphisms and Semi-Dualities of Graphs

Let G₁ and G₂ be undirected graphs, and ?₁(G ₁) and ?₂(G ₂) be families of edge sets of G₁ and G₂, respectively. An (?₁,?₂)-semi-isomorphism ofG ₁ ontoG ₂ is an edge bijection between G₁ and G₂ that induces an injection from ?₁(G ₁) to ?₂(G ₂). This concept generalizes a well known concept of a circuit isomorphism of graphs due to H. Whitney. If has a “dual nature” with respect to ?₂(G ₂) then the concept of (?₁,?₂)-semi-isomorphism of graphs turns into a concept of a (?₁,?₂)-semi-duality of graphs. This gives a natural generalization of the circuit duality of graphs due to H. Whitney. In this paper we investigate (?₁,?₂)-semi-isomorphisms and (?₁,?₂)-semi-dualities of graphs for various families ?₁(G ₁) and ?₂(G ₂). In particular, we consider families of circuits and cocircuits of graphs from this point of view, and obtain some strengthenings of Whitney’s 2-isomorphism theorem and Whitney’s planarity criterion for 3-connected graphs.     

Formulation of linear problems and solution by a universal machine

Using the predicate language for ordered fields a class of problems referred to aslinear problems is defined. This class contains, for example, all systems of linear equations and inequalities, all linear programming problems, all integer programming problems with bounded variables, all linear complementarity problems, the testing of whether sets that are defined by linear inequalities are semilattices, all satisfiability problems in sentenial logic, the rank-computation of matrices, the computation of row-reduced echelon forms of matrices, and all quadratic programming problems with bounded variables. A single, one, algorithm, to which we refer as theUniversal Linear Machine, is described. It solves any instance of any linear problem. The Universal Linear Machine runs in two phases. Given a linear problem, in the first phase a Compiler running on a Turing Machine generates alinear algorithm for the problem. Then, given an instance of the linear problem, in the second phase the linear algorithm solves the particular instance of the linear problem. The linear algorithm is finite, deterministic, loopless and executes only the five ordered field operations — additions, multiplications, subtractions, divisions and comparisons. Conversely, we show that for each linear algorithm there is a linear problem which the linear algorithm solves uniquely. Finally, it is shown that with a linear algorithm for a linear problem, one can solve certain parametric instances of the linear problem.Research was supported in part by the National Science Foundation Grant DMS 92-07409, by the Department of Energy Grant DE-FG03-87-ER-25028, by the United States—Israel Binational Science Foundation Grant 90-00434 and by ONR Grant N00014-92-J1142.Corresponding author.     

Boolean approach to planar embeddings of a graph

The purpose of this paper which is a sequel of “ Boolean planarity characterization of graphs ” [9] is to show the following results.

1. Both of the problems of testing the planarity of graphs and embedding a planar graph into the plane are equivalent to finding a spanning tree in another graph whose order and size are bounded by a linear function of the order and the size of the original graph, respectively.
2. The number of topologically non-equivalent planar embeddings of a Hamiltonian planar graphG is τ(G)=2 ^c(H)?1, wherec (H) is the number of the components of the graphH which is related toG.

     

Computing the volume is difficult

For every polynomial time algorithm which gives an upper bound (K) and a lower boundvol(K) for the volume of a convex setKR ^d , the ratio (K)/vol(K) is at least (cd/logd) ^d for some convex setKR ^d .This paper was partly written when both authors were on leave from the Mathematical Institute of the Hungarian Academy of Sciences, 1364 Budapest, P.O. Box 127, Hungary.     

Global optimization of univariate Lipschitz functions: I. Survey and properties

We consider the following global optimization problems for a univariate Lipschitz functionf defined on an interval [a, b]: Problem P: find a globally optimal value off and a corresponding point; Problem P: find a globally-optimal value off and a corresponding point; Problem Q: localize all globally optimal points; Problem Q: find a set of disjoint subintervals of small length whose union contains all globally optimal points; Problem Q: find a set of disjoint subintervals containing only points with a globally-optimal value and whose union contains all globally optimal points.We present necessary conditions onf for finite convergence in Problem P and Problem Q, recall the concepts necessary for a worst-case and an empirical study of algorithms (i.e., those ofpassive and ofbest possible algorithms), summarize and discuss algorithms of Evtushenko, Piyavskii-Shubert, Timonov, Schoen, Galperin, Shen and Zhu, presenting them in a simplified and uniform way, in a high-level computer language. We address in particular the problems of using an approximation for the Lipschitz constant, reducing as much as possible the expected length of the region of indeterminacy which contains all globally optimal points and avoiding remaining subintervals without points with a globally-optimal value. New algorithms for Problems P and Q and an extensive computational comparison of algorithms are presented in a companion paper.The research of the authors has been supported by AFOSR grants 0271 and 0066 to Rutgers University. Research of the second author has been also supported by NSERC grant GP0036426 and FCAR grant 89EQ4144. We thank N. Paradis for drawing some of the figures.