Dr William Pettersson

  • Research Associate (School of Computing Science)

Biography

I am a Research Associate at the School of Computing Science, University of Glasgow. I am working on the IP-MATCH EPSRC project, under the supervision of Dr David Manlove. The goal of such research is to allow the best possible allocation of resources. For instance, one outcome of the project is an allocation of kidney donors to patients, or the allocation of student doctors to hospitals.

Prior to coming to Glasgow, I have lived in various cities in Australia working on parallel exact integer multi-objective optimisation algorithms. I am also an accomplished graph theorist and topologist, specialising in algorithms in graph decompositions and combinatorial topology respectively.

Research interests

Very broadly, I am interested in solving problems with computers. This includes both complexity theory, the theoretical efficiency of an algorithm, as well as the practical running-time efficiency of an algorithm or approach.

Currently I am using integer programming to solve large and complex matching problems under the guidance of Dr David Manlove, and funded by EPSRC grant IP-MATCH. The goal of such research is to allow the best possible allocation of resources. For instance, one outcome of the project is an allocation of kidney donors to patients, or the allocation of student doctors to hospitals.

I have also spent significant time working on a software package called Regina. Regina is a mathematical software suite for combinatorial topologists. This work includes new algorithms, implementation of existing algorithms, and also various user-interface and user-experience updates.

My pet research projects are finding graph decompositions, often through computing. In this, I have researched various theoretical IP and LP techniques (such as constraint generation, Bender's decompositions) as well as more practical issues such as parallelisation techniques and even micro-optimisations in software. My big breakthrough in this area was the completion of the cycle decomposition problem, and I am currently, albeit slowly, working away on the Oberwolfach problem.

To aid various search engines, I here include some key research words and topics that interest me:

  • Parameterised complexity and fixed-parameter tractability
  • Graph algorithms, in particular colourings and decompositions
  • Exact multi-objective integer programming
  • Parallel algorithms
  • Graph decompositions
  • High performance computing

Additional information

I have previously worked on parallel algorithms for exact multi-objective integer optimisation with A.Prof Melih Ozlen. In this work, I implemented the following parallel algorithms

moip_aira - An implementation of EPP, SPREAD and CLUSTER, as detailed in <forthcoming>

boxfinder - An implementation of the algorithm from Kerstin Dächert, Kathrin Klamroth (2015). A linear bound on the number of scalarizations needed to solve discrete tricriteria optimization problems. Journal of Global Optimization, 61(4), 643--676

kppm - An implementation of the algorithm from C. Dhaenens, , J. Lemesre, E.G. Talbi (2008). K-PPM: A new exact method to solve multi-objective combinatorial optimization problems. European Journal of Operational Research, 200(1), 45-53.

I am also a developer of Regina, a suite of mathematical software for combinatorial topologists.

Publications

List by: Type | Date

Jump to: 2018 | 2017 | 2015 | 2014
Number of items: 7.

2018

Pettersson, W. and Ozlen, M. (2018) Multi-objective integer programming: synergistic parallel approaches. INFORMS Journal on Computing, (Accepted for Publication)

2017

Pettersson, W. and Ozlen, M. (2017) A parallel approach to bi-objective integer programming. ANZIAM Journal, 58, C69-C81. (doi:10.21914/anziamj.v58i0.11724)

Burton, B., Cabello, S., Kratsch, S. and Pettersson, W. (2017) The Parameterized Complexity of Finding a 2-Sphere in a Simplicial Complex. In: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), Hannover, Germany, 8-11 March 2017, 18:1-18:14. ISBN 9783959770286 (doi:10.4230/LIPIcs.STACS.2017.18)

2015

Bryant, D., Danziger, P. and Pettersson, W. (2015) Bipartite 2-ractorizations of complete multipartite graphs. Journal of Graph Theory, 78(4), pp. 287-294. (doi:10.1002/jgt.21806)

Burton, B. A. and Pettersson, W. (2015) An Edge-Based Framework for Enumerating 3-Manifold Triangulations. In: 31st International Symposium on Computational Geometry (SoCG 2015), Eindhoven, The Netherlands, 22-25 June 2015, pp. 270-284. ISBN 9783939897835 (doi:10.4230/LIPIcs.SOCG.2015.270)

2014

Bryant, D., Horsley, D. and Pettersson, W. (2014) Cycle decompositions V: Complete graphs into cycles of arbitrary lengths. Proceedings of the London Mathematical Society, 108(5), pp. 1153-1192. (doi:10.1112/plms/pdt051)

Burton, B. A. and Pettersson, W. (2014) Fixed Parameter Tractable Algorithms in Combinatorial Topology. In: International Computing and Combinatorics Conference (COCOON 2014), Atlanta, GA, USA, 4-6 Aug 2014, pp. 300-311. ISBN 9783319087825 (doi:10.1007/978-3-319-08783-2_26)

This list was generated on Tue Dec 11 19:35:44 2018 GMT.
Number of items: 7.

Articles

Pettersson, W. and Ozlen, M. (2018) Multi-objective integer programming: synergistic parallel approaches. INFORMS Journal on Computing, (Accepted for Publication)

Pettersson, W. and Ozlen, M. (2017) A parallel approach to bi-objective integer programming. ANZIAM Journal, 58, C69-C81. (doi:10.21914/anziamj.v58i0.11724)

Bryant, D., Danziger, P. and Pettersson, W. (2015) Bipartite 2-ractorizations of complete multipartite graphs. Journal of Graph Theory, 78(4), pp. 287-294. (doi:10.1002/jgt.21806)

Bryant, D., Horsley, D. and Pettersson, W. (2014) Cycle decompositions V: Complete graphs into cycles of arbitrary lengths. Proceedings of the London Mathematical Society, 108(5), pp. 1153-1192. (doi:10.1112/plms/pdt051)

Conference Proceedings

Burton, B., Cabello, S., Kratsch, S. and Pettersson, W. (2017) The Parameterized Complexity of Finding a 2-Sphere in a Simplicial Complex. In: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), Hannover, Germany, 8-11 March 2017, 18:1-18:14. ISBN 9783959770286 (doi:10.4230/LIPIcs.STACS.2017.18)

Burton, B. A. and Pettersson, W. (2015) An Edge-Based Framework for Enumerating 3-Manifold Triangulations. In: 31st International Symposium on Computational Geometry (SoCG 2015), Eindhoven, The Netherlands, 22-25 June 2015, pp. 270-284. ISBN 9783939897835 (doi:10.4230/LIPIcs.SOCG.2015.270)

Burton, B. A. and Pettersson, W. (2014) Fixed Parameter Tractable Algorithms in Combinatorial Topology. In: International Computing and Combinatorics Conference (COCOON 2014), Atlanta, GA, USA, 4-6 Aug 2014, pp. 300-311. ISBN 9783319087825 (doi:10.1007/978-3-319-08783-2_26)

This list was generated on Tue Dec 11 19:35:44 2018 GMT.