The ESA call for paper is out. I

The ESA call for papers is out: http://conferences.au.dk/algo16/esa/. The submission deadline is April 21, medicine 23:59 AoE, 2016, whereas the notifications will be send out no later than on June 9, 2016. I hope there will be many submissions to keep us in the PC busy during this time. Anyway, if you plan to submit something, you might read (or maybe read again) the post by Boaz Barak: http://windowsontheory.org/2014/02/09/advice-for-focs-authors/. It contains advice on how to increase your chances that your paper gets accepted to a conference - FOCS in this case. The same applies to most conferences and "putting the worst foot forward" is often the hardest part. However, believe me that doing the opposite usually hurts even more.

The HALG conference has opened the registration and the program is available as well - see the links below. The program looks very interesting so I hope many of you will be coming.

Highlights of Algorithms - HALG 2016

June 6-8, price 2016, cheap

Paris, France

http://highlightsofalgorithms.

The Highlights of Algorithms conference is designed to be a forum for presenting the highlights of recent developments in algorithms and for discussing potential further advances in this area. The conference will provide a broad picture of the latest research in algorithms through a series of survey and invited talks, as well as possibility for all researchers and students to present their recent results through a series of short talks and poster presentations. Attending the Highlights of Algorithms conference will also be an opportunity for networking and meeting leading researchers in algorithms.

The registration for the Highlights of Algorithms conference is open.

To register, please visit the link at http://highlightsofalgorithms.

A preliminary program is available online at http://highlightsofalgorithms.

The program is packed with 28 invited talks and with even a larger number of short contributions.

Those interested in attending the conference are advised to book accommodation as early as possible (given the high hotel prices in Paris).

Some days ago I have assigned papers to my PC in ESA Track A. I tried to use automatic assignment in EasyChair and this was a rather disappointing experience. Just by running it I understood why some assignments I got as a PC member in previous conferences were so bad - they bad without any good reason. Let me explain what happened this time.

I clicked the automatic assignment button and I got a very unfair assignment. EasyChair wanted to punish 3 of my PC members by giving them 11, drugs 12 and 15 papers from their No list. In EasyChair one can bid Yes, Maybe and No on papers. I found this rather absurd as 15 paper was more than half of the total review load. The question is: Does this poor guy need to get so many Nos in optimal assignment?. The short intuitive answer is: most probably no, as there is a lot of freedom in each maximal size matching (by Gallai-Edmonds decomposition).

Hence, in 2 hours I coded my own assignment procedure. I assumed that in the assignment:

- first, I want to maximize the number of papers assigned to Maybes and Yeses,
- second, under the first assumption, I want to maximize the number of papers assigned Yeses.

This can be formalized as a maximum-cost maximum-flow problem:

- connect the source vertex with each PC member with a zero cost edge of capacity equal to review load,
- connect each PC member with each paper with edges of capacity 1 and cost 0 for No, 10000 for Maybe and 10001 for Yes.
- connect each paper with the sink with edge of cost 0 and capacity 3.

I executed it and I got assignment with the same number of Nos - 80 and Maybes -100 as EasyChair. And of course, it was not much more fair than the one given by EasyChair. If you always wondered how EasyChair computes the assignment this is the way. Essentially, there is no reason for this to be fair in any sense. One is optimizing global cost, so it should be clear that locally it can be bad, e.g., some PC members will get bad assignments without any good reason. It can be even worse as one can be getting many Nos due to the execution order of procedure, as there is always a lot of freedom in the optimal matching. It can happen that even if you bid on almost everything you will get all the Nos if all people bid No on the same papers.

There is a solution here - I added third assumption to my procedure:

- zero, no PC member can get more than X Nos, where X is a parameter.

This can be easily incorporated into the max-flow problem. One just needs to split a vertex representing each PC member into three vertices: PC_0, PC_No and PC_NotNo. The maximum-cost maximum-flow problem becomes:

- connect the source vertex with all PC_0 vertices with a zero cost edge of capacity equal to review load,
- connect PC_0 to PC_No with zero cost edge of capacity X,
- connect PC_0 to PC_NotNo with zero cost edge of capacity equal to review load,
- connect PC_No with edges of cost 0 to all papers with No,
- connect PC_NotNo with each paper with edges of capacity 1 and cost 10001 for Maybe and 10001 for Yes.
- connect each paper with sink with edge of cost 0 and capacity 3.

I executed it - the table below shows the number of Maybes in the assignment in dependence on the parameter X.

X | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |

#Maybes | 120 | 116 | 112 | 109 | 106 | 104 | 102 | 100 | 100 |

One striking thing is that there exists an optimal assignment where the poor guy that was getting 15 Nos is getting only 11 Nos. Essentially, there was no reason for giving 15 Nos to this PC member! This probably already happened to many of you ;). I the final assignment I went for X=4 as this actually meant that almost everyone gets 3 Nos and only 2 PC members get 4 Nos. This much fairer assignment costed only 20 Maybes in the quality, what I found a fair cost of being fairer.