Jukka Suomela – Publications

Journal papers

[37]	Jukka Suomela. Survey of local algorithms. ACM Computing Surveys. To appear.
[36]	Patrik Floréen, Marja Hassinen, Joel Kaasinen, Petteri Kaski, Topi Musto, and Jukka Suomela. Local approximability of max-min and min-max linear programs. Theory of Computing Systems 49 (2011), pages 672–697.
[35]	Marja Hassinen, Joel Kaasinen, Evangelos Kranakis, Valentin Polishchuk, Jukka Suomela, and Andreas Wiese. Analysing local algorithms in location-aware quasi-unit-disk graphs. Discrete Applied Mathematics 159 (2011), pages 1566–1580.
[31]	Patrik Floréen, Petteri Kaski, Valentin Polishchuk, and Jukka Suomela. Almost stable matchings by truncating the Gale–Shapley algorithm. Algorithmica 58 (2010), pages 102–118.
[22]	Valentin Polishchuk and Jukka Suomela. A simple local 3-approximation algorithm for vertex cover. Information Processing Letters 109 (2009), pages 642–645.
[20]	Petteri Kaski, Aleksi Penttinen, and Jukka Suomela. Coordinating concurrent transmissions: A constant-factor approximation of maximum-weight independent set in local conflict graphs. Ad Hoc & Sensor Wireless Networks 6 (2008), pages 239–263.
[10]	Jukka Suomela. Approximability of identifying codes and locating-dominating codes. Information Processing Letters 103 (2007), pages 28–33.

Papers in refereed conference and workshop proceedings

[34]	Evangelos Kranakis, Oscar Morales Ponce, and Jukka Suomela. Planar subgraphs without low-degree nodes. 12th Algorithms and Data Structures Symposium (WADS), New York, NY, USA, August 2011.
[33]	Mika Göös and Jukka Suomela. Locally checkable proofs. 30th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), San Jose, CA, USA, June 2011.
[29]	Jukka Suomela. Distributed algorithms for edge dominating sets. 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), Zurich, Switzerland, July 2010.
[28]	Matti Åstrand and Jukka Suomela. Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks. 22nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Santorini, Greece, June 2010.
[25]	Matti Åstrand, Patrik Floréen, Valentin Polishchuk, Joel Rybicki, Jukka Suomela, and Jara Uitto. A local 2-approximation algorithm for the vertex cover problem. 23rd International Symposium on Distributed Computing (DISC), Elche, Spain, September 2009.
[23]	Patrik Floréen, Joel Kaasinen, Petteri Kaski, and Jukka Suomela. An optimal local approximation algorithm for max-min linear programs. 21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Calgary, Canada, August 2009.
[21]	Tanja Säily and Jukka Suomela. Comparing type counts: The case of women, men and -ity in early English letters. 28th Annual Conference of the International Computer Archive for Modern and Medieval English (ICAME), Stratford-upon-Avon, UK, May 2007.
[19]	Alon Efrat, Sándor P. Fekete, Poornananda R. Gaddehosur, Joseph S. B. Mitchell, Valentin Polishchuk, and Jukka Suomela. Improved approximation algorithms for relay placement. 16th Annual European Symposium on Algorithms (ESA), Karlsruhe, Germany, September 2008.
[18]	Valentin Polishchuk and Jukka Suomela. Optimal backlog in the plane. 4th International Workshop on Algorithmic Aspects of Wireless Sensor Networks (Algosensors), Reykjavík, Iceland, July 2008.
[17]	Patrik Floréen, Marja Hassinen, Petteri Kaski, and Jukka Suomela. Tight local approximation results for max-min linear programs. 4th International Workshop on Algorithmic Aspects of Wireless Sensor Networks (Algosensors), Reykjavík, Iceland, July 2008.
[15]	Patrik Floréen, Petteri Kaski, Topi Musto, and Jukka Suomela. Approximating max-min linear programs with local algorithms. 22nd IEEE International Parallel & Distributed Processing Symposium (IPDPS), Miami, FL, USA, April 2008.
[12]	Petteri Kaski, Aleksi Penttinen, and Jukka Suomela. Coordinating concurrent transmissions: A constant-factor approximation of maximum-weight independent set in local conflict graphs. 6th International Conference on Ad-Hoc Networks & Wireless (AdHoc-NOW), Morelia, Mexico, September 2007.
[11]	Patrik Floréen, Petteri Kaski, Topi Musto, and Jukka Suomela. Local approximation algorithms for scheduling problems in sensor networks. 3rd International Workshop on Algorithmic Aspects of Wireless Sensor Networks (Algosensors), Wrocław, Poland, July 2007.
[8]	Patrik Floréen, Petteri Kaski, and Jukka Suomela. A distributed approximation scheme for sleep scheduling in sensor networks. 4th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON), San Diego, CA, USA, June 2007.
[7]	Petteri Nurmi, Alfons Salden, Sian Lun Lau, Jukka Suomela, Michael Sutterer, Jean Millerat, Miquel Martin, Eemil Lagerspetz, and Remco Poortinga. A system for context-dependent user modeling. 2nd International Workshop on Context-Aware Mobile Systems (CAMS), Montpellier, France, October–November 2006.
[5]	Jukka Suomela. Approximating relay placement in sensor networks. 3rd ACM International Workshop on Performance Evaluation of Wireless Ad Hoc, Sensor, and Ubiquitous Networks (PE-WASUN), Torremolinos, Spain, October 2006.
[3]	Jukka Suomela. Computational complexity of relay placement in sensor networks. 32nd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), Měřín, Czech Republic, January 2006.
[1]	Jukka Kohonen and Jukka Suomela. Lessons learned in the challenge: making predictions and scoring them. 1st PASCAL Machine Learning Challenges Workshop (MLCW), Southampton, UK, April 2005.

Other work presented at refereed conferences and workshops

[30]	Patrik Floréen, Petteri Kaski, Valentin Polishchuk, and Jukka Suomela. Brief announcement: Distributed almost stable marriage. 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), Zurich, Switzerland, July 2010.
[16]	Marja Hassinen, Valentin Polishchuk, and Jukka Suomela. Local 3-approximation algorithms for weighted dominating set and vertex cover in quasi unit-disk graphs. 2nd International Workshop on Localized Algorithms and Protocols for Wireless Sensor Networks (LOCALGOS), Santorini Island, Greece, June 2008.
[13]	Michael A. Bender, Sándor P. Fekete, Alexander Kröller, Vincenzo Liberatore, Joseph S. B. Mitchell, Valentin Polishchuk, and Jukka Suomela. The minimum-backlog problem. 2nd International Conference on Mathematical Aspects of Computer and Information Sciences (MACIS), Paris, France, December 2007.
[9]	Petteri Nurmi, Joonas Kukkonen, Eemil Lagerspetz, Jukka Suomela, and Patrik Floréen. BeTelGeuse – a tool for Bluetooth data gathering. 2nd International Conference on Body Area Networks (BodyNets), Florence, Italy, June 2007.
[6]	Jukka Suomela. Locality helps sleep scheduling. Workshop on World-Sensor-Web (WSW), Boulder, CO, USA, October 2006.
[4]	Patrik Floréen, Joonas Kukkonen, Eemil Lagerspetz, Petteri Nurmi, and Jukka Suomela. BeTelGeuse: Tool for context data gathering via Bluetooth. 2nd Workshop on Context Awareness for Proactive Systems (CAPS), Kassel, Germany, June 2006.

Invited papers and popular articles

[32]	Jukka Suomela. Paikallinen laskettavuus. Tietojenkäsittelytiede 31 (2010), pages 57–69.
[26]	Christoph Lenzen, Jukka Suomela, and Roger Wattenhofer. Local algorithms: self-stabilization on speed. 11th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), Lyon, France, November 2009.

Theses

[24]	Jukka Suomela. Optimisation problems in wireless sensor networks: Local algorithms and local graphs. PhD thesis, University of Helsinki, Department of Computer Science. May 2009.
[2]	Jukka Suomela. Relay placement in sensor networks. MSc thesis, University of Helsinki, Department of Computer Science. October 2005.

Unpublished manuscripts

[39]	Mika Göös, Juho Hirvonen, and Jukka Suomela. Lower bounds for local approximation. Manuscript. January 2012.
[38]	Juho Hirvonen and Jukka Suomela. Distributed maximal matching: greedy is optimal. Manuscript. October 2011.
[27]	Matti Åstrand, Valentin Polishchuk, Joel Rybicki, Jukka Suomela, and Jara Uitto. Local algorithms in (weakly) coloured graphs. Manuscript. January 2010.
[14]	Patrik Floréen, Marja Hassinen, Petteri Kaski, and Jukka Suomela. Local approximation algorithms for a class of 0/1 max-min linear programs. Manuscript. February 2008.