MODIFIED APPROXIMATE PROXIMAL POINT ALGORITHMS FOR FINDING ROOTS OF MAXIMAL MONOTONE OPERATORS

§1　Introduction and preliminariesA set T Rn×Rnis called a monotone operator on Rn,if T has the property(x,y) ,(x′,y′)∈T 〈x -x′,y -y′〉≥0 ,where〈·,·〉denotes the inner product on Rn.T is maximal if(considered as a graph) itis not strictly contained in any other monotone operator on Rn.It is well known that thetheory of maximal monotone operators plays an important role in the study of convexprogramming and variational inequalities since itcan provide a powerful general framework…     

Finding 2-edge connected spanning subgraphs

This paper studies the NP-hard problem of finding a minimum size 2-edge connected spanning subgraph (2-ECSS). An algorithm is given that on an r-edge connected input graph G=(V,E) finds a 2-ECSS of size at most |V|+(|E|−|V|)/(r−1). For r-regular, r-edge connected input graphs for r=3, 4, 5 and 6, this gives approximation guarantees of and , respectively.     

Randomized on-line scheduling on three processors

We consider a randomized on-line scheduling problem where each job has to be scheduled on any of m identical processors. The objective is to minimize the expected makespan. We show that the competitive ratio of any randomized algorithm for m=3 processors must be strictly greater than .     

A pointwise convergence for Sobolev space functions

Let 1<p<∞, and k,m be positive integers such that 0(k−2m)pn. Suppose ΩRⁿ is an open set, and Δ is the Laplacian operator. We will show that there is a sequence of positive constants c_j such that for every f in the Sobolev space W^k,p(Ω), for all xΩ except on a set whose Bessel capacity B_k−2m,p is zero.     

Greedy sums of distinct squares

When a positive integer is expressed as a sum of squares, with each successive summand as large as possible, the summands decrease rapidly in size until the very end, where one may find two 's, or several 's. We find that the set of integers for which the summands are distinct does not have a natural density but that the counting function oscillates in a predictable way.

     

Embedding optimisation algorithms with Mosel

Algebraic modelling languages allow models to be implemented in such a way that they can easily be understood and modified. They are therefore a working environment commonly used by practitioners in Operations Research. Having once developed models, they need to be integrated inside the company information system. This step often involves embedding a model into a programming language environment: many existing algebraic modelling languages make possible to run parameterised models and subsequently retrieve their results, but without any facility for interacting with the model during the model generation or solution process.In this paper we show how to use the Mosel environment to implement complex algorithms directly in the modelling language.The Office cleaning problem is solved by a branch-and-cut algorithm, implemented entirely in the modelling language (including the definition of the callback function for the solver). Secondly, a cutting stock problem is solved by column generation, also implemented in the modelling language.AMS classification: 90Cxx, 65K05, 68N15     

Packet Reservation Window Multiple Access for Microcellular Voice/Data Transmission

We propose a new packet reservation multiple access (PRMA) scheme for the joint transmission of voice and data traffics in a microcellular medium. The collision resolution protocol within the system is based on a modification of the window random access algorithm, which has superior properties compared to the conventional slotted Aloha. The proposed algorithm, which we call packet reservation window multiple access (PRWMA), works in distinct modes for voice and data without prioritization, and the user performs slightly different operations depending on the information type. Simulation results show that PRWMA outperforms PRMA by a significant margin in terms of voice user capacity.     

Stability of a Pivoting Strategy for Parallel Gaussian Elimination

Gaussian elimination with partial pivoting achieved by adding the pivot row to the kth row at step k, was introduced by Onaga and Takechi in 1986 as means for reducing communications in parallel implementations. In this paper it is shown that the growth factor of this partial pivoting algorithm is bounded above by _n <#60; 3 ^n–1, as compared to 2 ^n–1 for the standard partial pivoting. This bound _n, close to 3 ^n–2, is attainable for class of near-singular matrices. Moreover, for the same matrices the growth factor is small under partial pivoting.This revised version was published online in October 2005 with corrections to the Cover Date.     

Extending the Balas-Yu bounds on the number of maximal independent sets in graphs to hypergraphs and lattices

A result of Balas and Yu (1989) states that the number of maximal independent sets of a graph G is at most ^p+1, where is the number of pairs of vertices in G at distance 2, and p is the cardinality of a maximum induced matching in G. In this paper, we give an analogue of this result for hypergraphs and, more generally, for subsets of vectors in the product of n lattices =₁××_n, where the notion of an induced matching in G is replaced by a certain binary tree each internal node of which is mapped into . We show that our bounds may be nearly sharp for arbitrarily large hypergraphs and lattices. As an application, we prove that the number of maximal infeasible vectors x=₁××_n for a system of polymatroid inequalities does not exceed max{Q,^logt/c(2Q,)}, where is the number of minimal feasible vectors for the system, , , and c(,) is the unique positive root of the equation 2^c(^c/log–1)=1. This bound is nearly sharp for the Boolean case ={0,1}ⁿ, and it allows for the efficient generation of all minimal feasible sets to a given system of polymatroid inequalities with quasi-polynomially bounded right-hand sides . This research was supported by the National Science Foundation (Grant IIS-0118635), and by the Office of Naval Research (Grant N00014-92-J-1375). The second and third authors are also grateful for the partial support by DIMACS, the National Science Foundation's Center for Discrete Mathematics and Theoretical Computer Science.Mathematics Subject Classification (2000):20E28, 20G40, 20C20