Ky Fan's N-matrices and linear complementarity problems

We consider the linear complementarity problem (LCP),w=Az + q, w0,z0,w ^T z=0, when all the off-diagonal entries ofA are nonpositive (the class of Z-matrices), all the proper principal minors ofA are positive and the determinant ofA is negative (the class of almost P-matrices). We shall call this the class of F-matrices. We show that ifA is a Z-matrix, thenA is an F-matrix if and only if LCP(q, A) has exactly two solutions for anyq0,q0, and has at most two solutions for any otherq. Research supported by AFOSR-89-0512.     

A Normal Law for Matchings

Dedicated to the memory of Paul Erdős, both for his pioneering discovery of normality in unexpected places, and for his questions, some of which led (eventually) to the present work.   For a simple graph G, let be the size of a matching drawn uniformly at random from the set of all matchings of G. Motivated by work of C. Godsil [11], we give, for a sequence and , several necessary and sufficient conditions for asymptotic normality of the distribution of , for instance

A search heuristic for the sequence-dependent economic lot scheduling problem

Almost all of the research on the economic lot scheduling problem (ELSP) has assumed that setup times are sequence-independent even though sequence-dependent problems are common in practice. Furthermore, most of the solution approaches that have been developed solve for a single optimal schedule when in practice it is more important to provide managers with a range of schedules of different length and complexity. In this paper, we develop a heuristic procedure to solve the ELSP problem with sequence-dependent setups. The heuristic provides a range of solutions from which a manager can choose, which should prove useful in an actual stochastic production environment. We show that our heuristic can outperform Dobson's heuristic when the utilization is high and the sequence-dependent setup times and costs are significant.     

An intersection problem for finite automata

A finite automaton with state space S and alphabet A can be thought of as a directed graph with vertex set S such that for each vertex t ϵ S the edges leaving t are in one-to-one correspondence with A. Motivated by a problem in logic, we propose a problem about intersections of languages accepted by finite automata and give some partial results.     

Asynchronous block-iterative primal-dual decomposition methods for monotone inclusions

Mathematical Programming - We propose new primal-dual decomposition algorithms for solving systems of inclusions involving sums of linearly composed maximally monotone operators. The principal...     

A Simplified Form of Block-Iterative Operator Splitting and an Asynchronous Algorithm Resembling the Multi-Block Alternating Direction Method of Multipliers

This paper develops what is essentially a simplified version of the block-iterative operator splitting method already proposed by the author and P. Combettes, but with more general initialization conditions. It then describes one way of implementing this algorithm asynchronously under a computational model inspired by modern high-performance computing environments, which consist of interconnected nodes each having multiple processor cores sharing a common local memory. The asynchronous implementation framework is then applied to derive an asynchronous algorithm which resembles the alternating direction method of multipliers with an arbitrary number of blocks of variables. Unlike earlier proposals for asynchronous variants of the alternating direction method of multipliers, the algorithm relies neither on probabilistic control nor on restrictive assumptions about the problem instance, instead making only standard convex-analytic regularity assumptions. It also allows the proximal parameters to range freely between arbitrary positive bounds, possibly varying with both iterations and subproblems.     

Approximate ADMM algorithms derived from Lagrangian splitting

This paper presents two new approximate versions of the alternating direction method of multipliers (ADMM) derived by modifying of the original “Lagrangian splitting” convergence analysis of Fortin and Glowinski. They require neither strong convexity of the objective function nor any restrictions on the coupling matrix. The first method uses an absolutely summable error criterion and resembles methods that may readily be derived from earlier work on the relationship between the ADMM and the proximal point method, but without any need for restrictive assumptions to make it practically implementable. It permits both subproblems to be solved inexactly. The second method uses a relative error criterion and the same kind of auxiliary iterate sequence that has recently been proposed to enable relative-error approximate implementation of non-decomposition augmented Lagrangian algorithms. It also allows both subproblems to be solved inexactly, although ruling out “jamming” behavior requires a somewhat complicated implementation. The convergence analyses of the two methods share extensive underlying elements.     

On the number of copies of one hypergraph in another

Given two hypergraphsH andG, letN(G, H) denote the number of subhypergraphs ofG isomorphic toH. LetN(l, H) denote the maximum ofN(G, H), taken over allG with exactlyl edges. In [1] Noga Alon analyzes the asymptotic behaviour ofN(l, H) forH a graph. We generalize this to hypergraphs: Theorem:For a hypergraph H with fractional cover number ρ*,N(G,H).=θ(lρ*) The interesting part of this is the upper bound, which is shown to be a simple consequence of an entropy lemma of J. Shearer. In a special case which includes graphs, we also provide a different proof using a hypercontractive estimate. Research supported in part by NSF.