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.     

Extended Bressoud-Wei and Koike skew Schur function identities

The Jacobi-Trudi identity expresses a skew Schur function as a determinant of complete symmetric functions. Bressoud and Wei extend this idea, introducing an integer parameter t?−1 and showing that signed sums of skew Schur functions of a certain shape are expressible once again as a determinant of complete symmetric functions. Koike provides a Jacobi-Trudi-style definition of universal rational characters of the general linear group and gives their expansion as a signed sum of products of Schur functions in two distinct sets of variables. Here we extend Bressoud and Wei's formula by including an additional parameter and extending the result to the case of all integer t. Then we introduce this parameter idea to the Koike formula, extending it in the same way. We prove our results algebraically using Laplace determinantal expansions.     

The satisfactory partition problem

The SATISFACTORY PARTITION problem consists in deciding if a given graph has a partition of its vertex set into two nonempty parts such that each vertex has at least as many neighbors in its part as in the other part. This problem was introduced by Gerber and Kobler [Partitioning a graph to satisfy all vertices, Technical report, Swiss Federal Institute of Technology, Lausanne, 1998; Algorithmic approach to the satisfactory graph partitioning problem, European J. Oper. Res. 125 (2000) 283-291] and further studied by other authors but its complexity remained open until now. We prove in this paper that SATISFACTORY PARTITION, as well as a variant where the parts are required to be of the same cardinality, are NP-complete. However, for graphs with maximum degree at most 4 the problem is polynomially solvable. We also study generalizations and variants of this problem where a partition into k nonempty parts (k?3) is requested.     

A graph partition problem

ＡＧＲＡＰＨＰＡＲＴＩＴＩＯＮＰＲＯＢＬＥＭ￥ＬＩＵＴＡＮＰＥＩ（刘彦佩）（ＤｅｐａｒｆｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ,ＮｏｒｔｈｅｒｎＪｉａｏｔｏｎｙＵｎｉｖｅｒｓｉｔｙ,Ｂｅｉｊｉｎｇ１０００４４,Ｃｈｉｎａ）ＡＵＲＯＲＡＭＯＲＧＡＮＡ（Ｄｅ...     

The partition bargaining problem

Consider the problem of partitioning n items among d players where the utility of each player for bundles of items is additive; so, player r has utility for item i and the utility of that player for a bundle of items is the sum of the 's over the items i in his/her bundle. Each partition S of the items is then associated with a d-dimensional utility vector V^S whose coordinates are the utilities that the players assign to the bundles they get under S. Also, lotteries over partitions are associated with the corresponding expected utility vectors. We model the problem as a Nash bargaining game over the set of lotteries over partitions and provide methods for computing the corresponding Nash solution, to prescribed accuracy, with effort that is polynomial in n. In particular, we show that points in the pareto-optimal set of the corresponding bargaining set correspond to lotteries over partitions under which each item, with the possible exception of at most d(d-1)/2 items, is assigned in the same way.     

A matrix partition problem

In the set of positive definite semi-integral symmetric matrices we propose a partition problem. Then by introducing the notion of “additively prime” we obtain the generating function for this problem. Finally we establish the analyticity of the generating function.     

On a cycle partition problem

Let G be any graph and let c(G) denote the circumference of G. We conjecture that for every pair c₁,c₂ of positive integers satisfying c₁+c₂=c(G), the vertex set of G admits a partition into two sets V₁ and V₂, such that V_i induces a graph of circumference at most c_i, i=1,2. We establish various results in support of the conjecture; e.g. it is observed that planar graphs, claw-free graphs, certain important classes of perfect graphs, and graphs without too many intersecting long cycles, satisfy the conjecture.This work is inspired by a well-known, long-standing, analogous conjecture involving paths.     

The maximum saving partition problem

The input to the MAXIMUM SAVING PARTITION PROBLEM consists of a set V={1,…,n}, weights w_i, a function f, and a family S of feasible subsets of V. The output is a partition (S₁,…,S_l) such that S_i∈S, and is maximized. We present a general -approximation algorithm, and improved algorithms for special cases of the function f.     

Universal number partition problem with divisibility

We examine a version of the Universal Number Partition Problem with a divisibility property referred to as the Universal Shelf Packing Problem (USPP). We show that if a shelf length is a product of powers of two primes the USPP is always partitionable. In the case where the shelf length is a product of three distinct primes we propose an efficient scheme to determine when such a case is not partitionable. We also show that a shelf length that is a product of powers of four or more primes always has at least one partition failure. Our analysis uses elementary number theory, known results related to the linear Diophantine Frobenius problem, and a new result on Frobenius gaps.     

On the modular sumset partition problem

A sequence m₁≥m₂≥?≥m_k of k positive integers isn-realizable if there is a partition X₁,X₂,…,X_k of the integer interval [1,n] such that the sum of the elements in X_i is m_i for each i=1,2,…,k. We consider the modular version of the problem and, by using the polynomial method by Alon (1999) [2], we prove that all sequences in Z/pZ of length k≤(p−1)/2 are realizable for any prime p≥3. The bound on k is best possible. An extension of this result is applied to give two results of p-realizable sequences in the integers. The first one is an extension, for n a prime, of the best known sufficient condition for n-realizability. The second one shows that, for n≥(4k)³, an n-feasible sequence of length k isn-realizable if and only if it does not contain forbidden subsequences of elements smaller than n, a natural obstruction forn-realizability.     

On a partition problem of Frobenius

We consider the following problem, which was raised by Frobenius: Given n relatively prime positive integers, what is the largest integer M(a₁, a₂, …, a_n) omitted by the linear form Σ_i=1ⁿa_ix_i, where the x_i are variable nonnegative integers. We give the solution for certain special cases when n = 3.     

Solution of the twisting problem for skew group algebras

LetK be any field of characteristicp>0 and letG be a finite group acting onK via a map τ. The skew group algebraK _τG may be nonsemisimple (precisely whenP|(H), H=Kert). In [1] necessary conditions were given for the existence of a class α∈H ²(G,K^*) which “twists” the skew group algebraK _τG into a semisimple crossed productK _τ ^αG . The “twisting problem” asks whether these conditions are sufficient. In [1] we showed that this is indeed so in many cases. In this paper we prove it in general. During the period of this research the second author was an Associate at the Center for Advanced Study, Urbana, Illinois.     

Approximation results for the weighted partition problem

We present several new standard and differential approximation results for the P₄-partition problem using the Hassin and Rubinstein algorithm [Information Processing Letters 63 (1997) 63–67]. Those results concern both minimization and maximization versions of the problem. However, the main point of this paper lies in the establishment of the robustness of this algorithm, in the sense that it provides good quality solutions for a variety of versions of the problem, under both standard and differential approximation ratios.     

The solution to the partition reconstruction problem

Given a partition λ of n, a k-minor of λ is a partition of n−k whose Young diagram fits inside that of λ. We find an explicit function g(n) such that any partition of n can be reconstructed from its set of k-minors if and only if k?g(n). In particular, partitions of n?k²+2k are uniquely determined by their sets of k-minors. This result completely solves the partition reconstruction problem and also a special case of the character reconstruction problem for finite groups.