Ruben Hoeksma

Personal homepage

My name is Ruben Hoeksma. I am a postdoctoral researcher at the Center for Mathematical Modeling at the University of Chile in Santiago. As an applied mathematics / computer science researcher, I have a broad interest in Discrete Mathematics, (Algorithmic) Game Theory, Scheduling, Optimization, Complexity and many related topics both of theoretical and applied nature. You can contact me using the contact information to the right (or below if you are on a smaller screen).

Among my various not (completely) research related interests are: sports in general and Korfball more specifically, computers, electronics and gadgets, board and video games, Magic: The Gathering, (computer) programming and photography.

View my CV here.

This is a list of my publications. Click the -icon to go to the official publication page. Click the -icon to download a preprint version of the publication (if available). Click the -icon to download a BibTeX file with the preferred citation format for the publication.

Journal articles

Approximation Algorithms for Connected Graph Factors of Minimum Weight. K. Cornelissen, R. Hoeksma, B. Manthey, N.S. Narayanaswamy, C.S. Rahul and M. Waanders. Theory of Computing. http://dx.doi.org/10.1007/s00224-016-9723-z, 2016.
Optimal Mechanism Design for a Sequencing Problem with Two-Dimensional Types R. Hoeksma and M. Uetz. Operations Research, 64(6):1438-1450, 2016.
Efficient implementation of Carathéodory’s theorem for the single machine scheduling polytope R. Hoeksma, B. Manthey and M. Uetz. Discrete Applied Mathematics, 215:136-145, 2016.

Peer-reviewed conference papers

Decomposition algorithm for the single machine scheduling polytope. R. Hoeksma, B. Manthey and M. Uetz. Combinatorial Optimization: Third International Symposium, ISCO 2014, Lisbon, Portugal, 5-7 March, 2014. Revised Selected Papers, pp. 280-291. Springer International Publishing, 2014.
Approximability of Connected Factors. K. Cornelissen, R. Hoeksma, B. Manthey, N.S. Narayanaswamy and C.S. Rahul. Approximation and Online Algorithms: 11th International Workshop, WAOA 2013, Sophia Antipolis, France, September 5-6, 2013. Revised Selected Papers, pp. 120-131. Springer International Publishing, 2014.
Two dimensional optimal mechanism design for a sequencing problem. R. Hoeksma and M. Uetz. Integer Programming and Combinatorial Optimization: 16th International Conference, IPCO 2013, Valparaíso, Chile, March 18-20, 2013. Proceedings, pp. 242-253. Springer Berlin Heidelberg, 2013.
The price of anarchy for minsum related machine scheduling. R. Hoeksma and M. Uetz. Approximation and Online Algorithms: 9th International Workshop, WAOA 2011, Saarbrücken, Germany, September 8-9, 2011. Revised Selected Papers, pp. 261-273. Springer International Publishing, 2012.

Theses

Mechanisms for scheduling games with selfish players. R. Hoeksma PhD thesis, University of Twente. CTIT Ph.D.- thesis series No. 14-342, 2015.
Price of anarchy for machine scheduling games with sum of completion times objective. R. Hoeksma R. Hoeksma, University of Twente. MSc Thesis, 2010.

These are some extremely boring photos. I'm planning to add some more interesting ones. Until then, these will have to do.

Apparently this is harder to maintain than I thought

A(n almost) mathematically correct introduction to Dots-and-Boxes

First posted: 19-04-2012 -- Last edit: 25-04-2012

During my second year as a mathematics student I got introduced to the game of Dot-and-Boxes (Kamertjeverhuur in Dutch) as a real mind game. Before that I had played it as a casual game, filling my writing pad during school hours. But as I said I got introduced to it as a real mind game and I have been playing it ever since (that sounds real cliché).

I would be lying if I said that I don't enjoy showing how good I am at this particular game, but that is not the point of this post. The point is that in the past days I wrote a short lesson programme for second year high school students, teaching them the mathematics behind the strategies that can be used for playing Dots-and-Boxes and I thought it would be nice to repeat some of it in this post.

In short the rules of the game are as follows. There is a play field consisting of nxm dots. Each turn one player connects two horizontally or vertically neighbouring dots with a line. If with the last line that player drew he closes one (or more) 'box(es)' he gets a point and has to draw another line. The player that has the most points when the board is full wins the game. With these easy rules, a notepad and a pencil you can play the game. Dots-and-Boxes is most regularly played on a 6 by 6 points field, i.e. 25 boxes.

The game becomes interesting once you notice the general ending of a game of Dots-and-Boxes. The last player gets to complete one long chain of 'boxes'. Normally this is even the longest chain and this wins the game for this player. With this information in mind, it seems interesting to know, who the last player will be. This is easily analyzed using Euler's formula for planar graphs. According to Wikipedia we have:

Euler's formula states that if a finite, connected, planar graph is drawn in the plane without any edge intersections, and v is the number of vertices, e is the number of edges and f is the number of faces (regions bounded by edges, including the outer, infinitely-large region), then

v - e + f = 2 .

In our case the number of vertices is the number of points (36 for 6x6). The number of regions is 26. So the number of edges (lines) is equal to 36 + 26 - 2 = 60. Now if we think about how many lines are placed in one move, this may vary. However, we do know that for each completed box, one extra line is placed within a move. This is true for every completed box except the last one, since there is no extra line to be placed. So out of 60 lines, there are 24 that are the result of a box being completed. So the total number of moves is equal to 60 - 24 = 36, exactly the number of dots (and this holds for any n-by-m field)!

So the number of moves is fixed and therefore the player that has the final move is fixed. This would mean that the winner of the game is also fixed, right? This would be correct, but there is a way to influence the number of moves: the double-cross. A double-cross is when a player instead of completing the last two boxes of a chain, makes a sacrifice move and leaves the last two to the other player (example picture coming shortly). Then those two boxes are completed with one single line and, as a concequence, one of the two extra lines because of those boxes is skipped. Therefore, after a double-cross, the total number of moves in the game is extended by one, shifting the last move to the other player.

If both players play well (enough), double-crosses only occur when a player gets a chain of three boxes or more. Therefore the tactics to Dots-and-Boxes are now as follows: count the number of dots (= the number of moves). If this number is even the first player has to make sure that there are an even number of 'long chains' on the board in the end, the second player tries to get an odd number of 'long chains'. If the number of dots is odd, it is the other way around. This basic idea should help you win against most players. Of course if you want to beat me, you should evolve some tactics on how to get to an even/odd number of 'long chains'.

You can download the Dutch lesson to Dots-and-Boxes here. Or go to my links page.

Have fun!