A note on a new variant of Murty’s ranking assignments algorithm

In this paper a variant of Murtys algorithm for ranking assignments according to cost is presented. It is shown that the worst-case computational complexity is better in this variant than in the original form of the algorithm. Computational results comparing three methods for ranking assignments are reported. They show that the behaviour of the new variant is also better in practice.Received: March 2003, Revised: March 2003, AMS classification: 90C27, 05C85Marta Pascoal: The research of Marta Pascoal was developed within CISUC and partially supported by the Portuguese Ministry of Science and Technology (MCT), under PRAXIS XXI Project of JNICT.     

Finding simple t-designs with enumeration techniques

Lattice basis reduction in combination with an efficient backtracking algorithm is used to find all (4 996 426) simple 7-(33,8,10) designs with automorphism group PΓL(2, 32). © 1998 John Wiley & Sons, Inc. J Combin Designs 6:79–90, 1998     

Factors of Functions,AC and Recursive Analogues

We investigate certain statements about factors of unary functions (in particular,factors of permutations) which have connections with weak forms of the axiom of choice. We discuss more extensively the fine structure of Howard and Rubin's Form 314 (which concerns bireflectivity of permutations) from [4]. Some of our set‐theoretic results have also interesting recursive versions.     

Set packing relaxations of some integer programs

This paper is about set packing relaxations of combinatorial optimization problems associated with acyclic digraphs and linear orderings, cuts and multicuts, and set packings themselves. Families of inequalities that are valid for such a relaxation as well as the associated separation routines carry over to the problems under investigation. Received: September 1997 / Accepted: November 1999?Published online June 8, 2000     

Rigid Unary Functions and the Axiom of Choice

We shall investigate certain statements concerning the rigidity of unary functions which have connections with (weak) forms of the axiom of choice.     

Restricted b‐factors in bipartite graphs and t‐designs

We present a new equivalence result between restricted b‐factors in bipartite graphs and combinatorial t‐designs. This result is useful in the construction of t‐designs by polyhedral methods. We propose a novel linear integer programming formulation, which we call GDP, for the problem of finding t‐designs that has a noteworthy advantage compared to the traditional set‐covering formulation. We analyze some polyhedral properties of GPD, implement a branch‐and‐cut algorithm using it and solve several instances of small designs to compare with another point‐block formulation found in the literature. © 2006 Wiley Periodicals, Inc. J Combin Designs 14: 169–182, 2006     

Facets of the polytope of the asymmetric travelling salesman problem with replenishment arcs

The Asymmetric Travelling Salesman Problem with Replenishment Arcs (RATSP) is a new class of problems arising from work related to aircraft routing. Given a digraph with cost on the arcs, a solution of the RATSP, like that of the Asymmetric Travelling Salesman Problem, induces a directed tour in the graph which minimises total cost. However the tour must satisfy additional constraints: the arc set is partitioned into replenishment arcs and ordinary arcs, each node has a non-negative weight associated with it, and the tour cannot accumulate more than some weight limit before a replenishment arc must be used. To enforce this requirement, constraints are needed. We refer to these as replenishment constraints.In this paper, we review previous polyhedral results for the RATSP and related problems, then prove that two classes of constraints developed in V. Mak and N. Boland [Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs, Technical Report TR M05/03, School of Information Technology, Deakin University, 2005] are, under appropriate conditions, facet-defining for the RATS polytope.     

On the combinatorial structure of chromatic scheduling polytopes

Chromatic scheduling polytopes arise as solution sets of the bandwidth allocation problem in certain radio access networks, supplying wireless access to voice/data communication networks for customers with individual communication demands. To maintain the links, only frequencies from a certain spectrum can be used, which typically causes capacity problems. Hence it is necessary to reuse frequencies but no interference must be caused by this reuse. This leads to the bandwidth allocation problem, a special case of so-called chromatic scheduling problems. Both problems are NP-hard, and there do not even exist polynomial time algorithms with a fixed quality guarantee.As algorithms based on cutting planes have shown to be successful for many other combinatorial optimization problems, the goal is to apply such methods to the bandwidth allocation problem. For that, knowledge on the associated polytopes is required. The present paper contributes to this issue, exploring the combinatorial structure of chromatic scheduling polytopes for increasing frequency spans. We observe that the polytopes pass through various stages—emptyness, non-emptyness but low-dimensionality, full-dimensionality but combinatorial instability, and combinatorial stability—as the frequency span increases. We discuss the thresholds for this increasing “quantity” giving rise to a new combinatorial “quality” of the polytopes, and we prove bounds on these thresholds. In particular, we prove combinatorial equivalence of chromatic scheduling polytopes for large frequency spans and we establish relations to the linear ordering polytope.     

The Topology of the Coloring Complex

In a recent paper, E. Steingrímsson associated to each simple graph G a simplicial complex _G, referred to as the coloring complex of G. Certain nonfaces of _G correspond in a natural manner to proper colorings of G. Indeed, the h-vector is an affine transformation of the chromatic polynomial _G of G, and the reduced Euler characteristic is, up to sign, equal to |_G(–1)|–1. We show that _G is constructible and hence Cohen-Macaulay. Moreover, we introduce two subcomplexes of the coloring complex, referred to as polar coloring complexes. The h-vectors of these complexes are again affine transformations of _G, and their Euler characteristics coincide with _G(0) and –_G(1), respectively. We show for a large class of graphs—including all connected graphs—that polar coloring complexes are constructible. Finally, the coloring complex and its polar subcomplexes being Cohen-Macaulay allows for topological interpretations of certain positivity results about the chromatic polynomial due to N. Linial and I. M. Gessel.Research financed by ECs IHRP Programme, within the Research Training Network Algebraic Combinatorics in Europe, grant HPRN-CT-2001-00272.     

The combinatorics of graphical unitary group approach to many electron correlation

The combinatorics of Gel'fand states which are useful in the graphical unitary group approach to many electron correlation problem and spin free quantum chemistry is considered. Using operator theoretic methods it is shown that the generators of Gel'fand states are S-functions.