Obituary: Nicos Christofides, 1942 – 2019

Professor Nicos Christofides

Nigel Meade, Emeritus Professor of Quantitative Finance, pays tribute to the late Professor Christofides, who died in October 2019.

Nicos left his native Cyprus to take A level courses in Folkestone where he found the English Channel much less inviting than the eastern Mediterranean. In 1960, he began his lifelong association with Imperial by winning a scholarship to study Electrical Engineering. He said that he obtained the scholarship despite being able to answer only two of the five questions set, which was an uncommon experience for him. Apparently, he was the candidate with the best attempt at the answers.  

After graduating with First Class Honours in 1966, he stayed in Electrical Engineering to complete a PhD titled “The origins of load losses in induction motors with cast aluminium rotors” under a joint supervision that involved Nobel Prize winner Dennis Gabor. He was awarded the Ferranti medal for his thesis. He fondly recalled the award of this medal as it was the first official event that he attended with his girlfriend and future wife, Ann. 

Pioneer in vehicle routing algorithms

In 1968, he changed focus towards a different problem area, by taking a lectureship in the Management Engineering Section of Mechanical Engineering (which sequentially evolved into the Department of Management Science, the Management School, and finally the Business School).  

Here he started his work in combinatorial optimisation and graph theory, an area where practical problems are often so complex that they cannot be easily solved optimally. Nicos, together with department head Sam Eilon, were pioneers in vehicle routing algorithms. In 1971, Nicos published his first book with Sam: “Distribution Management: mathematical modelling and practical analysis”. 

The Travelling Salesman Problem

Nicos is perhaps best known for the Travelling Salesman Problem (TSP), a classic example of these computationally difficult problems (called NP-Hard in complexity theory) and is one of the most intensively studied problems in optimization: The salesman has to find the shortest route to visit a set of towns, visiting each town exactly once and coming back to the beginning.  In a pre-internet, pre-Google Maps world where small computers were the size of a wardrobe, vehicle routing (a version of the TSP) was an early application of graph theory. Unfortunately, even though Nicos had devised innovative algorithms, the necessary coordinate data were not yet available.

His sons still recall the months, if not years, where the family dining room table was covered with maps, coloured pens and tracing paper as Nicos and his wife spent many evenings digitising the UK road system, where junctions became nodes, roads became arcs. It was at this time that fundamental new ideas on his famous work on bounds on Travelling Salesman were formed.   

In 1975 Nicos published his seminal and pioneering book “Graph Theory: An Algorithmic Approach” and shortly afterwards Nicos and family took a sabbatical year in North America visiting several universities and developing research projects. Nicos held visiting professor positions at a number of major US universities with visits to Carnegie-Mellon, University of Rochester, Berkeley and Stanford. It was during his time working on the TSP, among other combinatorial optimization problems, that he made lasting friendships with mathematicians George Dantzig and Don Knuth. 

Nicos worked on finding upper and lower bounds for an optimal solution for the TSP which was put together as a hastily prepared conference presentation following strong encouragement from his friends. A famous and longer version of the conference presentation was prepared during this sabbatical “Worst-case analysis of a new heuristic for the travelling salesman problem” and was first published as a research report in 1976 at Carnegie-Mellon in Pittsburgh PA, where he was visiting the Management Sciences Research Group. Nicos never published this paper in an academic journal, apparently one journal accepted the paper with a few minor corrections, but he never got around to making the corrections! He called the algorithm related to this bound “the three-halves bound” and it is now known as “The Christofides Algorithm”, which found a circuit for the salesman that was less than 3/2 times longer than the optimal solution. In the general case, the Christofides Algorithm remains the best ‘worst-case’ scenario.  

His graph theory algorithms were applied to routing vehicles, unloading oil tankers, packing containers, cutting fabric, network flows and warehouse logistics among other things. Nearly 50 years ago, Nicos developed and fully commercialized, industrial quality vehicle routing software, that is still used today.

Contracts with NASA and IBM

During the 1970s and 1980s, Nicos helped create a research centre in Italy (SOGESTA, in Urbino), and supervised many research students who explored the developing field of heuristic algorithms for problems in areas such as vehicle routing and two-dimensional cutting. In 1979, Nicos released his third book “Combinatorial Optimization”.  

He became Professor of Operational Research in 1982. During the 1980s, Nicos started his work on the analysis of images, condensing an image to a combination of basic shapes. Over the following decades, he developed algorithms for image compression that allowed images to be stored using a fraction of the memory taken by the raw image. The crucial property of this compression was that the image could be restored with no, or a priori controllable, information loss. If images are created at vast expense and need to be transmitted as efficiently as possible without loss of quality, for example from a space probe, this no loss property is very attractive. As a result, Nicos had consultancy contracts with NASA and IBM relating to his Image Compression work.

Collaborations with industry

In parallel with his academic career, Nicos was always very active in consulting for industry in a wide range of operational research projects.  Nicos had a unique ability of explaining elaborate and mathematically complex problems to the layman in a way that made extremely hard solutions sound easy. This skill naturally led him to forge extensive relationships with business leaders and he consulted for a diverse set of industries, including the Oil and Gas sector (BP, ENI, PTT), pseudo Government Agencies (NASA, Centre for Disease Control), Telecoms (BT, C&W) and nearly every major multinational bank in the financial sector.  

A popular teacher

In 1990, Nicos and Gerry Salkin set up the Centre for Quantitative Finance (CQF) within the Management School, which he then directed for 17 years. The CQF was one of the largest and most highly respected research groups in ?nance in the world and was sponsored by a large number of distinguished American, European and Japanese ?nancial institutions and corporates. Nicos’s focus was on supervising PhD students in tackling ‘real world’ problems in financial mathematics and risk management. Scores of CQF PhD alumni are now spread throughout finance centres worldwide. In total, Nicos was involved in the supervision of over 200 PhD students.  

Very popular as a teacher, Nicos was always ready to explain even the most difficult concepts in terms of easily understood ideas. It is said by his long-standing friend, Professor Tony Constantinides, that “the best way to learn from Nicos is to disagree with him”. 

A renaissance man

Aside from work, Nicos was a renaissance man with an encyclopaedic general knowledge and was a prolific reader and writer. He enjoyed both the art and science of photography and collected fountain pens and leather-bound journals where he wrote exquisite and detailed academic notes. He also had an extensive collection of marbles and wooden tops from his childhood, with which he would often try to impress his grandchildren. 

On retirement from Imperial College London, Nicos was made Professor Emeritus of Quantitative Finance in 2009. During his academic career he published over 150 papers in quality journals and four books on optimization and quantitative finance.  

In 2018, Nicos was devastated by the death of his wife, Ann, but resolved to keep working hard until his death the following year.  His two sons, Alexander and Simon, and three grandchildren, Hugo, Ivan and Lola survive him.