On partitioning the orbitals of a transitive permutation group

Let be a permutation group on a set with a transitive normal subgroup . Then acts on the set of nontrivial -orbitals in the natural way, and here we are interested in the case where has a partition such that acts transitively on . The problem of characterising such tuples , called TODs, arises naturally in permutation group theory, and also occurs in number theory and combinatorics. The case where is a prime-power is important in algebraic number theory in the study of arithmetically exceptional rational polynomials. The case where exactly corresponds to self-complementary vertex-transitive graphs, while the general case corresponds to a type of isomorphic factorisation of complete graphs, called a homogeneous factorisation. Characterising homogeneous factorisations is an important problem in graph theory with applications to Ramsey theory. This paper develops a framework for the study of TODs, establishes some numerical relations between the parameters involved in TODs, gives some reduction results with respect to the -actions on and on , and gives some construction methods for TODs.

     

On the exhaustivity of simplicial partitioning

During the last 40 years, simplicial partitioning has been shown to be highly useful, including in the field of nonlinear optimization, specifically global optimization. In this article, we consider results on the exhaustivity of simplicial partitioning schemes. We consider conjectures on this exhaustivity which seem at first glance to be true (two of which have been stated as true in published articles). However, we will provide counter-examples to these conjectures. We also provide a new simplicial partitioning scheme, which provides a lot of freedom, whilst guaranteeing exhaustivity.     

On partitioning of hypergraphs

We study edge-isoperimetric problems (EIP) for hypergraphs and extend some technique in this area from graphs to hypergraphs. In particular, we establish some new results on a relationship between the EIP and some extremal poset problems, and apply them to obtain an exact solution of the EIP for certain hypergraph families. We also show how to solve the EIP on hypergraphs in some cases when the link to posets does not work. Another outcome of our results is a new series of hypergraphs admitting nested solutions in the EIP.     

On the possibilities of a phase transition of superconducting type in the Gross-Neveu model

It is shown that calculation of the anomalous expectation values for the massless Gross-Neveu model in the Hartree-Fock approximation indicates the presence of an ordinary chiral phase transition if the coupling constant has the normal sign (g>0) and of a different transition of the superconductivity type ifg<0.State University, St. Petersburg. Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 103, No. 2, pp. 295–298, May, 1995.     

On the complexity of partitioning sparse matrix representations

A standard representation of a sparse matrix is a structure where non-zero elements are linked in rows and columns. A general graph structure corresponding to this representation is defined. The problem of partitioning such a graph into fixed size blocks, so that the number of inter-block links is minimized, is shown to be NP-complete.Supported by NSF Grant MCS-8004337.     

On possibilities of the method of homogeneous solutions in the mixed problem of elasticity theory for a half-strip

The mixed plane boundary value problem for an elastic half-strip under kinematic loading of its endface and lateral sides free of force loads is examined. An asymptotic is obtained for the coefficients of the series expansion of the displacement vector in homogeneous solutions. Regularization of the series in homogeneous solutions is proposed which would permit computation of the stress field on the half-strip enface.Translated from Teoreticheskaya i Prikladnaya Mekhanika, No. 18, pp. 3–8, 1987.     

On the tour partitioning heuristic for the unit demand capacitated vehicle routing problem

The tour partitioning heuristic for the vehicle routing problem assumes an unlimited supply of vehicles. If the number of vehicles is fixed, this heuristic may produce infeasible solutions. We modify the heuristic to guarantee feasibility in this situation and we analyze the worst-case performance of the modified heuristic.     

Noising methods for a clique partitioning problem

This paper deals with the application of noising methods to a clique partitioning problem for a weighted graph. The aim is to study different ways to add noise to the data, and to show that the choice of the noise-adding-scheme may have some impact on the performance of these methods. Among the noise-adding-schemes described here, two of them are totally new, leading to the “forgotten vertices” and to the “forgotten edges” methods. We also experimentally study a generic noising method that automatically tunes its parameters. For each noise-adding-scheme, we compare a variant which inserts descents and a variant which does not.     

On the integer properties of scheduling set partitioning models

Many scheduling problems, arising in the transportation industry, can be posed as massive set partitioning zero-one integer programmes. For reasons of computational complexity it is generally unrealistic to attempt to solve the model in this form using conventional integer linear programming. By the imposition of additional structure, derived from the real-world problem but not already implicit in the mathematical model, it is possible to significantly reduce the effects of computational complexity and provide an effective method of obtaining good feasible solutions.In this paper, recent results in graph theory concerning natural integer properties of set partitioning integer programmes are discussed. These results motivate the development of further implicit constraints which simultaneously reduce the dimensionality and increase the proportion of integer basic feasible solutions of the set partitioning linear programme.     

On the complexity of partitioning graphs into connected subgraphs

This paper is mainly concerned with the computational complexity of determining whether or not the vertices of a graph can be partitioned into equal sized subsets so that each subset induces a particular type of graph. Many of the NP-completeness results are for planar graphs. These are proved using a planar version of 3-dimensional matching.     

A projection technique for partitioning the nodes of a graph

LetG=(N,E) be an undirected graph. We present several new techniques for partitioning the node setN intok disjoint subsets of specified sizes. These techniques involve eigenvalue bounds and tools from continuous optimization. Comparisons with examples taken from the literature show these techniques to be very successful.     

On partitioning the edges of graphs into connected subgraphs

For any positive integer s, an s-partition of a graph G = (V, E) is a partition of E into E₁ ∪ E₂ ∪…? ∪ E_k, where ∣E_i∣ = s for 1 ≤ i ≤ k ? 1 and 1 ≤ ∣E_k∣ ≤ s and each E_i induces a connected subgraph of G. We prove

• (i) If G is connected, then there exists a 2-partition, but not necessarily a 3-partition;
• (ii) If G is 2-edge connected, then there exists a 3-partition, but not necessarily a 4-partition;
• (iii) If G is 3-edge connected, then there exists a 4-partition;
• (iv) If G is 4-edge connected, then there exists an s-partition for all s.

     

Performance of a genetic algorithm for the graph partitioning problem

The performance of the genetic algorithm (GA) for the graph partitioning problem (GPP) is investigated by comparison with standard heuristics on well-known benchmark graphs. In general, there is a case where a practical performance of a conventional genetic approach, which performs only simple operations without a local search strategy, is not sufficient. However, it is known that a combination of GA and local search can produce better solutions. From this practice, we incorporate a simple local search algorithm into the GA. In particular, the search ability of the GA is compared with standard heuristics such as multistart local search and simulated annealing, which use the same neighborhood structure of the simple local search, for solving the GPP. Experimental results show that the GA performs better than its competitors.     

On the complexity of some Euclidean problems of partitioning a finite set of points

Problems of partitioning a finite set of Euclidean points (vectors) into clusters are considered. The criterion is to minimize the sum, over all clusters, of (1) squared norms of the sums of cluster elements normalized by the cardinality, (2) squared norms of the sums of cluster elements, and (3) norms of the sum of cluster elements. It is proved that all these problems are strongly NP-hard if the number of clusters is a part of the input and are NP-hard in the ordinary sense if the number of clusters is not a part of the input (is fixed). Moreover, the problems are NP-hard even in the case of dimension 1 (on a line).     

A silent duel over a cake

The division of a cake by two players is modelled by means of a silent game of timing. It is shown that this game has a unique Nash equilibrium. The strategies of the Nash equilibrium are explicitly given.I thank Peter Borm, Eric van Damme, Feico Drost, Harold Houba, Jos Potters, Stef Tijs and the referees for their comments.     

On the validity of a front-oriented approach to partitioning large sparse graphs with a connectivity constraint

In this paper we consider the problem of partitioning large sparse graphs, such as finite element meshes. The heuristic which is proposed allows to partition into connected and quasi-balanced subgraphs in a reasonable amount of time, while attempting to minimize the number of edge cuts. Here the goal is to build partitions for graphs containing large numbers of nodes and edges, in practice at least 10⁴. Basically, the algorithm relies on the iterative construction of connected subgraphs. This construction is achieved by successively exploring clusters of nodes called fronts. Indeed, a judicious use of fronts ensures the connectivity of the subsets at low cost: it is shown that locally, i.e. for a given subgraph, the complexity of such operations grows at most linearly with the number of edges. Moreover, a few examples are given to illustrate the quality and speed of the heuristic.The work of this author was partially supported by the DGA/DRET under contract 93-1192 and by the Army Research Office under contract DAAL03-91-C-0047 (Univ. Tenn. subcontract ORA4466.04 Amendment 1).The work of this author was partially supported by the National Science Foundation under contract ASC 92-01266, the Army Research Office under contract DAAL03-91C-0047 (Univ. Tenn. subcontract ORA4466.04 Amendment 1), and ONR under contract ONR-N00014-92-J-1890.     

Approximation algorithm for the problem of partitioning a sequence into clusters

We consider the problem of partitioning a finite sequence of Euclidean points into a given number of clusters (subsequences) using the criterion of the minimal sum (over all clusters) of intercluster sums of squared distances from the elements of the clusters to their centers. It is assumed that the center of one of the desired clusters is at the origin, while the center of each of the other clusters is unknown and determined as the mean value over all elements in this cluster. Additionally, the partition obeys two structural constraints on the indices of sequence elements contained in the clusters with unknown centers: (1) the concatenation of the indices of elements in these clusters is an increasing sequence, and (2) the difference between an index and the preceding one is bounded above and below by prescribed constants. It is shown that this problem is strongly NP-hard. A 2-approximation algorithm is constructed that is polynomial-time for a fixed number of clusters.