The generalized assignment problem: Valid inequalities and facets

Three classes of valid inequalities based upon multiple knapsack constraints are derived for the generalized assignment problem. General properties of the facet defining inequalities are discussed and, for a special case, the convex hull is completely characterized. In addition, we prove that a basic fractional solution to the linear programming relaxation can be eliminated by a facet defining inequality associated with an individual knapsack constraint.Partial financial support under NSF grant #CCR-8812736.Partial financial support under NSF grant #DMS-8606188.     

Facet identification for the symmetric traveling salesman polytope

Several procedures for the identification of facet inducing inequalities for the symmetric traveling salesman polytope are given. An identification procedure accepts as input the support graph of a point which does not belong to the polytope, and returns as output some of the facet inducing inequalities violated by the point. A procedure which always accomplishes this task is calledexact, otherwise it is calledheuristic. We give exact procedures for the subtour elimination and the 2-matching constraints, based on the Gomory—Hu and Padberg—Rao algorithms respectively. Efficient reduction procedures for the input graph are proposed which accelerate these two algorithms substantially. Exact and heuristic shrinking conditions for the input graph are also given that yield efficient procedures for the identification of simple and general comb inequalities and of some elementary clique tree inequalities. These procedures constitute the core of a polytopal cutting plane algorithm that we have devised and programmed to solve a substantial number of large-scale problem instances with sizes up to 2392 nodes to optimality.Partial financial support by NSF grant DMS8508955 and ONR grant R&T4116663.Work done while visiting New York University. Partial financial support by a New York University Research Challenge Fund grant and ONR grant R&T4116663.     

Nevanlinna inequality for intersection of divisors

A Nevanlinna-type inequality is proved for holomorphic mapf:C ^m →M and for intersection of sections of a line bundle overM, in which the intersection may not be pure dimensional and the map may be degenerate. Partial financial support was provided by the NSF under grant number DMS-8922760.     

An efficient algorithm for the minimum capacity cut problem

Given a finite undirected graph with nonnegative edge capacities the minimum capacity cut problem consists of partitioning the graph into two nonempty sets such that the sum of the capacities of edges connecting the two parts is minimum among all possible partitionings. The standard algorithm to calculate a minimum capacity cut, due to Gomory and Hu (1961), runs in O(n ⁴) time and is difficult to implement. We present an alternative algorithm with the same worst-case bound which is easier to implement and which was found empirically to be far superior to the standard algorithm. We report computational results for graphs with up to 2000 nodes.Partial financial support by NSF grant DMS8508955 and ONR grant R&T4116663.Work done while visiting New York University. Partial financial support by a New York University Research Challenge Fund grant and ONR grant R&T4116663.     

Groups with small Dehn functions and bipartite chord diagrams

We introduce a new invariant of bipartite chord diagrams and use it to construct the first examples of groups with Dehn function n²log n. Some of these groups have undecidable conjugacy problem. Our groups are multiple HNN extensions of free groups. We show that n²log n is the smallest Dehn function of a multiple HNN extension of a free group with undecidable conjugacy problem. Both authors were supported in part by the NSF grants DMS 0245600 and DMS 0455881. In addition, the research of the first author was supported in part by the Russian Fund for Basic Research 05-01-00895, the research of the second author was supported in part by the NSF grant DMS 9978802 and the US-Israeli BSF grant 1999298. Received: February 2005; Revision: September 2005; Accepted: September 2005     

Fréchet Embeddings of Negative Type Metrics

We show that every n-point metric of negative type (in particular, every n-point subset of L ₁) admits a Fréchet embedding into Euclidean space with distortion , a result which is tight up to the O(log log n) factor, even for Euclidean metrics. This strengthens our recent work on the Euclidean distortion of metrics of negative into Euclidean space. S. Arora supported by David and Lucile Packard Fellowship and NSF grant CCR-0205594. J.R. Lee supported by NSF grant CCR-0121555, NSF 0514993, NSF 0528414 and an NSF Graduate Research Fellowship.     

Rates of growth and sample moduli for weighted empirical processes indexed by sets

Summary Probability inequalities are obtained for the supremum of a weighted empirical process indexed by a Vapnik-ervonenkis class C of sets. These inequalities are particularly useful under the assumption P({CC:P(C)<t})»0 as t»0. They are used to obtain almost sure bounds on the rate of growth of the process as the sample size approaches infinity, to find an asymptotic sample modulus for the unweighted empirical process, and to study the ratio P _n/P of the empirical measure to the actual measure.Research supported under an NSF Postdoctoral Fellowship grant No. MCS 83-11686, and in part by NSF grant No. DMS-8301807     

Sharpening the LYM inequality

The level sequence of a Sperner familyF is the sequencef(F)={f _i (F)}, wheref _i (F) is the number ofi element sets ofF . TheLYM inequality gives a necessary condition for an integer sequence to be the level sequence of a Sperner family on ann element set. Here we present an indexed family of inequalities that sharpen theLYM inequality.Research supported in part by Alexander v. Humboldt-StiftungResearch supported in part by NSF under grant DMS-86-06225 and AFOSR grant OSR-86-0078Research supported in part by NSF grant CCR-8911388Research supported in part by OTKA 327 0113     

A theory of recursive dimension for ordered sets

The classical theorem of R. P. Dilworth asserts that a partially ordered set of width n can be partitioned into n chains. Dilworth's theorem plays a central role in the dimension theory of partially ordered sets since chain partitions can be used to provide embeddings of partially ordered sets in the Cartesian product of chains. In particular, the dimension of a partially-ordered set never exceeds its width. In this paper, we consider analogous problems in the setting of recursive combinatorics where it is required that the partially ordered set and any associated partition or embedding be described by recursive functions. We establish several theorems providing upper bounds on the recursive dimension of a partially ordered set in terms of its width. The proofs are highly combinatorial in nature and involve a detailed analysis of a 2-person game in which one person builds a partially ordered set one point at a time and the other builds the partition or embedding.This paper was prepared while the authors were supported, in part, by NSF grant ISP-80-11451. In addition, the second author received support under NSF grant MCS-80-01778 and the third author received support under NSF grant MCS-82-02172.     

The partition problem

In this paper we describe several forms of thek-partition problem and give integer programming formulations of each case. The dimension of the associated polytopes and some basic facets are identified. We also give several valid and facet defining inequalities for each of the polytopes.Partial Support from NSF Grants DMS 8606188 and ECS 8800281 is gratefully acknowledged.     

KK-Theories for topological algebras

We propose a unified construction of generalizedKK-functors on various categories of topological algebras ranging between the two extreme cases: the categories of discrete algebras and the category ofC ^*-algebras. Usual functorial properties of these functors are derived.Supported in part by an NSF grant.     

Weighted norm inequalities for operators of potential type and fractional maximal functions

In this paper, we study two-weight norm inequalities for operators of potential type in homogeneous spaces. We improve some of the results given in [6] and [8] by significantly weakening their hypotheses and by enlarging the class of operators to which they apply. We also show that corresponding results of Carleson type for upper half-spaces can be derived as corollaries of those for homogeneous spaces. As an application, we obtain some necessary and sufficient conditions for a large class of weighted norm inequalities for maximal functions under various assumptions on the measures or spaces involved.Research of the first author was supported in part by NSERC grant A5149.Research of the second author was supported in part by NSF grant DMS93-02991.     

Valid inequalities for MIPs and group polyhedra from approximate liftings

In this paper, we present an approximate lifting scheme to derive valid inequalities for general mixed integer programs and for the group problem. This scheme uses superadditive functions as the building block of integer and continuous lifting procedures. It yields a simple derivation of new and known families of cuts that correspond to extreme inequalities for group problems. This new approximate lifting approach is constructive and potentially efficient in computation. J.-P. P. Richard was supported by NSF grant DMI-348611.     

New higher-order equiaffine invariants

We introduce new affine invariants for smooth convex bodies. Some sharp affine isoperimetric inequalities are established for the new invariants. Partially supported by an NSERC grant and an FRDP grant. Partially supported by an NSF grant, an FRG-NSF grant and a BSF grant.     

Interpolation, correlation identities, and inequalities for infinitely divisible variables

We present an interpolation formula for the expectation of functions of infinitely divisible (i.d.) variables. This is then applied to study the association problem for i.d. vectors and to present new covariance expansions and correlation inequalities. Acknowledgements and Notes. The research of C. Houdré was supported in part by an NSF Mathematical Sciences Post-Doctoral Fellowship and by an NSF-NATO Postdoctoral Fellowship and by the NSF grant No. DMS-98032039. This research was completed while V. Pérez-Abreu was visiting the Georgia Institute of Technology.     

A General Fredholm Theory II: Implicit Function Theorems

This is the second paper in a series introducing a generalized Fredholm theory in a new class of smooth spaces called polyfolds. In general, these spaces are not locally homeomorphic to open sets in Banach spaces. The current paper develops the Fredholm theory in M-polyfold bundles. It consists of a transversality and a perturbation theory. In upcoming papers the generalized Fredholm theory will be applied to the Floer Theory, the Gromov–Witten Theory and the Symplectic Field Theory H.H.’s research partially supported by NSF grant DMS-0603957. K.W.’s research partially supported by NSF grant DMS-0606588.     

A Logarithmic-Quadratic Proximal Prediction-Correction Method for Structured Monotone Variational Inequalities

Inspired by the Logarithmic-Quadratic Proximal (LQP) method for variational inequalities, we present a prediction-correction method for structured monotone variational inequalities. Each iteration of the new method consists of a prediction and a correction. Both the predictor and the corrector are obtained easily with tiny computational load. In particular, the LQP system that appears in the prediction is approximately solved under significantly relaxed inexactness restriction. Global convergence of the new method is proved under mild assumptions. In addition, we present a self-adaptive version of the new method that leads to easier implementations. Preliminary numerical experiments for traffic equilibrium problems indicate that the new method is effectively applicable in practice. Presented at the 6th International conference on Optimization: Techniques and Applications, Ballarat Australia, December 9–11, 2004. This author was supported by NSFC Grant 10571083, the MOEC grant 20020284027 and Jiangsu NSF grant BK2002075     

Settling time bounds forM/G/1 queues

This paper addresses the question of how long it takes for anM/G/1 queue, starting empty, to approach steady state. A coupling technique is used to derive bounds on the variation distance between the distribution of number in the system at timet and its stationary distribution. The bounds are valid for allt. This research was supported in part by a grant from the AT&T Foundation and NSF grant DCR-8351757.     

A CLT for a band matrix model

A law of large numbers and a central limit theorem are derived for linear statistics of random symmetric matrices whose on-or-above diagonal entries are independent, but neither necessarily identically distributed, nor necessarily all of the same variance. The derivation is based on systematic combinatorial enumeration, study of generating functions, and concentration inequalities of the Poincaré type. Special cases treated, with an explicit evaluation of limiting variances, are generalized Wigner and Wishart matrices. O.Z. was partially supported by NSF grant number DMS-0302230.     

A remark on congruences for coefficients of Faber polynomials

Faber polynomials appear when weight zero Hecke operators act on the modular j-invariant. They are polynomials in j with rational integral coefficents. Using the theory of p-adic modular forms we establish some congruences and divisibilities for these coefficients. 2000 Mathematics Subject Classification Primary—11F33 Supported by NSF grant DMS-0501225.