 fProf. Kate SmithMiles Monash UniversityThe NoFreeLunch Theorem tells us that, without prior knowledge of the properties of an instance of a problem, we cannot expect any single algorithm to outperform all others across all instances. If an algorithm performs exceptionally well on a certain class of instances, there will always be some other class of instances where it is outperformed by another algorithm. Understanding how the properties of an instance affect algorithm performance is the key to being able to articulate the strengths and weaknesses of an algorithm, and to anticipate when it is likely to be better than others. In this talk I will present a new methodology for achieving this goal, and demonstrate its applicability to optimization, although it generalizes to other problem domains. The methodology involves: visualizing the set of all possible instances based on features that correlate with difficulty; statistical generalization of algorithm performance in this instance space, shown as a footprint where an algorithm's performance is deemed to be good; and then measuring the relative area of the footprint of different algorithms. The methodology is applied to provide insights into optimization algorithm performance on the Travelling Salesman Problem and graph colouring.

 Dr. Irina Dumitrescu IBM Research Australia The Traveling Salesman Problem with Pickup and Delivery (TSPPD) is defined on a graph containing pickup and delivery vertices between which there exists a onetoone relationship. The problem consists of determining a minimum cost tour such that each pickup vertex is visited before its corresponding delivery vertex. We discuss modelling the TSPPD as an integer linear program and we investigate its polyhedral structure. We determine the dimension of the TSPPD polytope and present several valid inequalities, some of which are facet defining. Finally, we show how some of the valid inequalities can be integrated into a branchandcut algorithm. 
 Prof. Jerzy Filar Flinders UniversityWe consider the famous Hamiltonian cycle problem (HCP) embedded in a Markov decision process (MDP). More specifically, we consider a moving object on a graph G where, at each vertex, a controller may select an arc emanating from that vertex according to a probabilistic decision rule. A stationary policy is simply a control where these decision rules are time invariant. Such a policy induces a Markov chain on the vertices of the graph. Therefore, HCP is equivalent to a search for a stationary policy that induces a 01 probability transition matrix whose nonzero entries trace out a Hamiltonian cycle in the graph. A consequence of this embedding is that we may consider the problem over a number of, alternative, convex  rather than discrete  domains. These include: (a) the space of stationary policies, (b) the more restricted but, very natural, space of doubly stochastic matrices induced by the graph, and (c) the associated spaces of socalled "occupational measures". 
 Dr. Ali Eshragh Adelaide UniversityIn this talk, we introduce a certain polytope, H, induced by a particular discounted Markov decision process corresponding to a given graph G. It has been proved that if the graph G is Hamiltonian, then corresponding to each Hamiltonian cycle in G there exists an extreme point in H, namely, a Hamiltonian extreme point. We concentrate on ErdösRenyi random graph G{n,p}, where n is the total number of nodes and p is the probability of having an arc between any pair of nodes. We show that the set of all extreme points of polytope H corresponding to a random graph G{n,p} can be partitioned into five subsets and derive the expected cardinality of each of them. These results indicate that the ratio of expected number of Hamiltonian extreme points to all extreme points decays rapidly as the latter is of the order O(n^{n}). However, an adaptation of the polytope H, will be shown to have much more favourable ratios of this type. In particular, we constrain H by appropriately designed, efficient linear constraints, to obtain a new polytope WH ⊂ H. Numerical results suggest the following two conjectures on WH: (i) Extreme points of polytope WH can be generated, uniformly, in polynomial time, (ii) The rational frequency of Hamiltonian extreme points in WH is bounded below by a rational function of n. In order to prove (i), one may try to design a random walk on extreme points of WH which has the property that the underlying Markov chain is rapidly mixing. To prove (ii), a good approach might be to extract certain geometric properties of extreme points of WH and try to use the same notion as utilized in H. We support our conjectures by numerical results. If we prove these two conjectures, we can assert that for any given graph G the Hamiltonian cycle problem can be solved, with high probability, in polynomial time. 
 Dr. Michael Haythorpe Flinders UniversityWe construct polyhedra, defined by a polynomiallybounded number of linear constraints dependent on the structure of a 3regular graph Γ, that are guaranteed to be nonempty if Γ contains Hamiltonian cycles, but which may be empty otherwise. Then, if such a set of constraints is found to be inconsistent, we may conclude that Γ is nonHamiltonian. We present a (nontrivial) proof of the inconsistency of constraints produced for bridge graphs. A further refinement of this approach which takes advantage of particular kbonds (where k = 1, 2, 3) is shown, along with experimental evidence to indicate that almost all 3regular nonHamiltonian graphs can be identified by this approach. 
 Prof. Martin Savelsbergh University of NewcastleThe vehicle routing problem (VRP), introduced by Dantzig and Ramser in 1959, is an important problem in the fields of transportation, distribution, and logistics. The VRP seeks to serve a number of customers with a fleet of vehicles at minimum cost. Many variants of the VRP have been proposed and investigated to accommodate complexities encountered in reallife settings, e.g., time windows and pickup and deliveries. Once an assignment of customers to vehicles is known, minimizing the cost for a vehicle corresponds to solving a Traveling Salesman Problem (TSP), often a TSP with side constraints. We explore computational challenges encountered when solving a TSP with time window flexibility and a TSP with delivery quantity flexibility. 
 Dr. Richard Taylor Defence, Science and Technology OrganisationWe shall discuss an optimisation form of the Hamilton cycle problem and goodness measures of heuristics for this problem. This will include discussion of the boundary between what we currently know and what we would like to know. 
 Mr. Pouya Baniasadi Flinders UniversityWe propose a partitioning of the set of unlabelled, connected cubic graphs into two disjoint subsets named genes and descendants, where the cardinality of the descendants is much larger than that of the genes. The key distinction between the two subsets is the presence of special edge cut sets, called crackers, in the descendants. We show that every descendant can be constructed by starting from a finite set of genes, and introducing the required crackers by special breeding operations. We prove that it is always possible to identify which genes are used to generate a descendant, and provide inverse operations that enable their reclamation. A number of interesting properties of genes, such as planarity and nonHamiltonicity, may be inherited by the descendant, and we therefore propose a natural polynomial algorithm that decomposes a descendant into its ancestor genes. We conjecture that each descendant can only be generated by starting with a unique set of ancestor genes. 
 A/Prof. Vladimir Ejov Flinders UniversityWe present a polynomial complexity heuristic for solving the Hamiltonian Cycle Problem in an undirected graph of order fn. Although finding a Hamiltonian cycle is not theoretically guaranteed, we have observed that the heuristic is successful even in cases where such cycles are extremely rare, and it also performs very quickly on all HCP examples of large graphs listed on TSPLIB web page. The heuristic owes its name to a visualisation of its iterations. All vertices of the graph are placed on a given circle in some order. The graph's edges are classified as either snakes or ladders, with snakes forming arcs of the circle and ladders forming its chords. The heuristic strives to place exactly fn snakes on the circle, thereby forming a Hamiltonian cycle. The snakes and ladders heuristic (SLH) uses transformations, inspired by kopt algorithms such as the, now classical, LinKernighan heuristic to reorder the vertices on the circle in order to transform some ladders into snakes and vice versa. The use of a suitable stopping criterion ensures the heuristic terminates in polynomial time. This is a joint work with P. Baniasadi, J. Filar, M. Haythorpe and S. Rossomakhine (all Flinders University). 
 Scheduling Arc Capacity Changes over Time so as to Maximize Dynamic Flow in a NetworkProf. Natashia Boland University of NewcastleMany real life systems can be viewed as a network with arc capacities, supporting the flow of a commodity, in which maximizing throughput of the commodity in the network is a key concern. Whilst this suggests a maximum flow model would be appropriate, in fact, the real network is not static: capacities change over time. Changes can arise in strategic planning as a result of capacity expansion, with either new arcs or extra capacity added to existing arcs, subject to budget constraints on limiting what can be built in a time period. In tactical planning, capacity changes can occur as a result of maintenance activities, leading to reductions in arc capacities for the period of the maintenance. To obtain maximum throughput, it is important to select the schedule for capacity changes (such as addition of new arcs, or timing of maintenance jobs) that leads to minimum loss of flow. This leads to a model in which arc capacity change "jobs" need to be scheduled so as to maximize the total flow in the network over time. The resulting combinatorial optimization problem provides a rich field for analysis: computational complexity, approximation algorithms, and asymptotic analysis are all of interest. Some initial results in these directions will be discussed. 
 Prof. David Shmoys Cornell UniversityWe will survey a number of recent results that yield improved approximation algorithms for variants of the traveling salesman problem (TSP); an rapproximation algorithm for an optimization is a polynomialtime algorithm that is guaranteed to find a feasible solution of objective function value within a factor of r of optimal. We shall briefly discuss recent results of Oveis Gharan, Saberi, & Singh and Mumka & Svensson for the graphical TSP, Asadpour, Goemans, Madry, Oveis Gharan, & Saberi for the asymmetric TSP, but we shall focus on a result of An, Kleinberg, and Shmoys for the st path traveling salesman problem, which provides an approximation algorithm that is guaranteed to find a solution of cost within a factor of the golden ratio of optimal in polynomial time. In the st path TSP, we are given pairwise distances among n points that satisfy the triangle inequality, and two specified endpoints s and t; the problem is to find a shortest Hamiltonian path between s and t. Hoogeveen showed that the natural variant of the classic TSP algorithm of Christofides is a 5/3approximation algorithm for this problem, and this asymptotically tight bound in fact has been the best approximation ratio known until now. We modify this algorithm so that it randomly chooses the initial spanning tree based on an optimal solution to a natural linear programming relaxation, rather than a minimum spanning tree; we prove this simple but crucial modification leads to an improved approximation ratio, surpassing the 20yearold barrier set by the natural Christofides' algorithm variant. 
 Coherent Structures in Geophysical FlowsA/Prof. Gary Froyland University of New South WalesThe detection and tracking of minimally dispersive regions in fluid flow is of importance in oceanography and atmospheric science. The strong nondispersiveness of coherent objects such as eddies (resp. vortices) makes them excellent transporters of water (resp. air) with different physical properties to the surrounding water (resp. air). I will describe a method for identifying and tracking coherent regions in flows, which is based on the classical minimax characterisation of eigenvalues of compact selfadjoint operators. 
 Some Problems in Hamiltonian cyclesProf. Brendan McKay Australian National UniversityWe present a random selection of problems regarding Hamiltonian cycles. These include Hamiltonian cycles in various types of planar graphs, as well as hypohamiltonian graphs. Algorithms for finding cycles will be discussed in this context. 
 Everything You Always Wanted to Know About the Second Hamiltonian Cycle ProblemDr. János Barát Monash UniversityStarring Thomassen, Thomason, Haxell, Fleischner, Edmonds, Sheehan, Jackson. featuring Deletion and contraction, Hamiltonian pairs, Lollipop method, Cubic and other regular graphs, Algorithms: polynomial and exponential, Lovasz local lemma, Chromatic roots, etc. 
 Prof. Gordon Royle University of Western AustraliaThe Tutte polynomial of a graph is a 2variable polynomial associated a graph that is a universal deletion/contraction invariant, in the sense that ANY graphical parameter that can be computed by a deletion/contraction recurrence, such as the chromatic polynomial, number of spanning trees, reliability polynomial and so on, is an evaluation of the Tutte polynomial. The ubiquity of the Tutte polynomial is further evidenced by the fact that it appears in statistical physics under the guise of the qstate Potts model, and there is a substantial literature in Physics on the computational and theoretical aspects of the Tutte polynomial. As deletion/contraction is inherently exponential in nature and many of these graphical parameters are known to be NPhard to compute individually, computing the Tutte polynomial is hard both in theory and in practice, making datadriven computational exploration and experimentation difficult. In this talk, I will survey various approaches to computing the Tutte polynomial, some of the problems that have been resolved or refined as a result of computational experimentation, and some of the many interesting remaining problems. 
 On Hamiltonian Cycles in Planar GraphsA/Prof. David Wood Monash UniversityThe study of Hamiltonian cycles in cubic planar graphs has a rich history, originally motivated by Tait's conjecture that every cubic 3connected planar graph is Hamiltonian (which implies the 4 colour theorem). Tutte disproved Tait's conjecture, which lead Barnette to conjecture that every bipartite cubic 3connected planar graph is Hamiltonian. We prove a new sufficient condition for a cubic 3connected planar graph to be Hamiltonian. This condition is most easily described as a property of the dual graph. Let G be a planar triangulation. Then the dual G^{*} is a cubic 3connected planar graph, and G^{*} is bipartite if and only if G is Eulerian. We prove that if the vertices of G are (improperly) coloured blue and red, such that the blue vertices cover the faces of G, there is no blue cycle, and every red cycle contains a vertex of degree at most 4, then G^{*} is Hamiltonian. This result implies the following special case of Barnette's Conjecture: if G is an Eulerian planar triangulation, whose vertices are properly coloured blue, red and green, such that every redgreen cycle contains a vertex of degree 4, then G^{*} is Hamiltonian. We also prove some results highlighting the limitations of using a proper colouring of G as a starting point for proving Barnette's Conjecture. This is joint work with Helmut Alt, Michael Payne, and Jens Schmidt. 
 Dr. Giang Nguyen Adelaide UniversityWe explore the relationship between the geometric structure of a graph and its spectrum, by investigating certain functionals of graph eigenvalues and showing that they are related to geodesics on the graph. In particular, we present an intriguing selfsimilar structure that groups cubic graphs according to the number of geodesics of certain lengths, and discuss the location of nonHamiltonian graphs within this selfsimilar structure. 
 Dr. David Glynn Flinders UniversityWe look at any simple 3connected cubic graph on n vertices and discuss one of its matroid representations, which involves a "quantum set" of n lines in binary space PG(r,2) with r=n/2. The edge 3colourings of the graph correspond bijectively to another related set of lines of this space, and the Hamilton cycles correspond to the points on precisely one (or an odd number) of these lines. It follows (from codingtheoretic or algebraic considerations) that the number of Hamilton cycles through any edge is even and there cannot be just one or two Hamilton cycles in the graph. W.T. Tutte and C.A.B. Smith obtained these results but from different methods. We discuss other methods such as a way to find all edge 3colourings from the solutions of a single polynomial equation over GF(4). So the graph is a "snark" if and only if there are no solutions. Another method is to determine Hamilton cycles in bipartite cubic graphs from a binary determinant condition of degree r1 in r+1 variables where the graph has 2r vertices. 
 A/Prof. Graham Farr Monash UniversityPlanarisation is the process of removing part of a graph to leave behind a planar subgraph. This is important in many applications where networks must be laid out on twodimensional surfaces such as a screen or a circuit layer. We consider the Maximum Induced planar Subgraph problem, in which planarisation is achieved by removal of vertices. We have linked this to the problem of fragmentability of graphs, where we seek the smallest proportion of vertices in a graph whose removal breaks the graph into small (bounded size) pieces. This talk describes our algorithms for these and related problems, which give the best performance guarantees to date for them. 
 Prof. Yinyu Ye Stanford UniversityLinear programming (LP), together with the simplex method, remain a core topic in Operations Research, Computer Science and Mathematics since 1947. Due to the relentless research effort, a linear program can be solved today one million times faster than it was done thirty years ago. Businesses, large and small, now use LP models to control manufacture inventories, price commodities, design civil/communication networks, and plan investments. LP even becomes a popular subject taught in under/graduate and MBA curriculums, advancing human knowledge and promoting science education. The aim of the talk is to describe several recent exciting progresses on LP and the simplex method, include counter examples to the Hirsch conjecture, some pivoting rules and their exponential behavior, strongly polynomialtime bounds of the simplex and policyiteration methods for solving Markov Decision Process (MDP) and turnbased zerosum game with constant discount factors, the strongly polynomialtime complexity of the simplex method for solving deterministic MDP regardless discounts, etc. 