Algorithmics, Social choice, Market Design, and Other Topics

I just came across the following new report: http://arxiv.org/find/cs/1/au:+Trofimov_M/0/1/0/all/0/1 . The complexity of the graph isomoprphism problem is a longstanding open problem. Therefore, it will be interesting to check if the problem has finally been resolved.

ICALP accepted paper list is now public: http://icalp10.inria.fr/index.php?n=Main.AcceptedPapers . Some papers which caught my eyes were: Nikhil Bansal and Subhash Khot. Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Nicole Immorlica and Hamid Mahini. The cooperative game theory foundations of network bargaining games Jian Li, Ke Yi and Qin Zhang. Clustering with Diversity Tobias Harks and Max Klimm. On the Existence of Pure Nash Equilibria in Weighted Congestion Games Anupam Gupta, Viswanath Nagarajan and R Ravi. Thresholded Covering Algorithms for Robust and Max-Min Optimization Allan Borodin and Brendan Lucier. On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions Loukas Georgiadis. Testing $2$-vertex connectivity and computing pairs of vertex-disjoint $s$-$t$ paths in digraphs T-H. Hubert Chan, Elaine Shi and Dawn Song. Private and Continual Release of...

In the latest AMS feature column, Joseph Malkevitch discusses mathematics involved in sports scheduling and related fairness and optimization questions in choosing rankings or winners.

The 11th Max-Planck Summer School Advanced Course on the Foundations of Computer Science (ADFOCS 2010) will be held from August 2 - 6, 2010 in Saarbruecken, Germany. The topic is `Approximation Algorithms and Algorithmic Game Theory’ and the invited speakers are Christos Papadimitriou,Vijay Vazirani and Guido Schaefer. Topics covered in the course will be `Computing Equilibria’, `Traditional to Novel Market Models: the Quest for the 'Right' One’ and `Cost Sharing and Approximation Algorithms’.

An interesting workshop on algorithmic mechanism design : http://econ.eecs.northwestern.edu/FMD2010/#schedule