As Editor-in-Chief of The Computer Journal, published by Oxford University Press on behalf of BCS, The Chartered Institute for IT, it is my honour to select the recipient of the annual Wilkes Award, awarded to the authors of the best paper published in the previous year’s volume. The key judging criteria for the Award are originality and quality of theme and treatment, as assessed by an expert judging panel.
We are pleased to announce this year’s winning and runner up papers for the 2023 Wilkes Award for Volume 65 (2022):
Winning paper
Two-Hop Relay Deployment Based on User Trajectory in Wireless Networks
Zhiyao Li, Siru Ouyang, Xiaofeng Gao and Guihai Chen
The Computer Journal, Volume 65, Issue 12 (December 2022), pp.3106-3122
https://doi.org/10.1093/comjnl/bxab130
This paper addresses relay deployment in wireless networks. Prior work generally assumed user locations were fixed and known in advance, an assumption the authors argue does not hold in practice now that user trajectory data can be collected routinely from mobile devices. They reformulate the problem around maximising users’ connection time as they move through an area, rather than simply maximising area coverage, and introduce demand nodes: weighted grid cells derived from historical trajectory data that capture where users tend to pass through or linger. This converts deployment into a demand node coverage problem, which the authors prove is NP-complete via a reduction from the circle covering problem. For the resulting problem they design an approximation algorithm, the Submodular Iterative Deployment Algorithm, which extends a standard greedy framework for submodular set cover with a partition technique so that it additionally respects a network connectivity constraint, and for which they derive a formally proven, constant-factor approximation guarantee. The approach is evaluated on five real GPS trajectory datasets spanning two university campuses, a city centre, a theme park and a state fair, with coverage performance ranging from around 60% to over 96% depending on the dataset. The authors offer specific, evidenced explanations for the weaker cases rather than treating the variation as unexplained noise: New York’s elongated, strip-like trajectories sit awkwardly with the two-hop limit, while the Statefair dataset’s small sample size undermines the accuracy of its inferred demand nodes. The combination of a practically motivated reformulation of an established problem, a proven complexity result, an algorithm with a rigorously derived approximation guarantee, and thorough, honestly reported empirical validation made this a strong choice for the Award.
Runner up
How Many Pop-Stacks Does It Take To Sort A Permutation?
Michael Albert and Vincent Vatter
The Computer Journal, Volume 65, Issue 10 (October 2022), pp.2610-2614
https://doi.org/10.1093/comjnl/bxab092
The runner-up paper is a concise piece of combinatorics: it gives a new proof that any permutation of length n can be sorted using at most n−1 passes through a pop-stack, a restricted stack that empties completely on every pop rather than releasing items one at a time. The result itself was already implicit in a 1982 paper by Ungar, written for an unrelated problem in combinatorial geometry. The authors’ contribution is a clearer route to that result, built around two intermediate sorting operations they call tumble and flip and inspired by Knuth’s zero-one principle from sorting network theory, with the intermediate steps shown to be of some interest in their own right. It is a reminder that not every prize-worthy contribution needs new machinery or extensive evaluation; a clearer route to an existing result, carefully argued, has its own value.
You can browse previous winners of the Wilkes Award, and find out more about the Award itself. Thank you also to the 2023 Wilkes Award judging panel:
- Professor Chris Mitchell, Royal Holloway, University of London, UK
- Professor Alan Marshall, University of Liverpool, UK
The award is named after Sir Maurice Wilkes (1913-2010), Director of the Cambridge University Computer Laboratory from 1945 to 1980, throughout the development of stored program computers starting with EDSAC, which ran the first realistic programs on a stored-program electronic computer in 1949. He went on to invent microprogramming, and, with David Wheeler and Stanley Gill, developed an early programming system based on subroutines and labels that shaped how software was written for decades afterwards. Wilkes was also the founding President of the British Computer Society (1957-60), received the ACM A.M. Turing Award in 1967, and was knighted for his services to computing in 2000.
Digital Society & Policy 