The STACS 2012 accepted papers are out. STACS is in Paris and starts on February 29.
The most noteworthy article for my taste, at first glance, is the 13/9-approximation for Graphic TSP by Marcin Mucha, available here. (In some sense this is old news: the paper will be presented at STACS, but was published on Arxiv in August.) They improve the analysis of the Moemke-Svensson paper from last Spring (presented last month at FOCS; was published on Arxiv in April).
Here's a quote: We present an improved analysis of the cost of the circulation used in the construction of the TSP tour/path. [...] The circulation used [by Moemke and Svensson] consists of two parts: the ”core” part based on an extreme optimal solution to the Held-Karp relaxation of TSP, and the ”correction” part that adds enough flow to the core part to make it feasible. We improve bounds on costs of both part; in particular we show that the second part is in a sense free. As for the first part, similarly to the original proof of Moemke and Svensson, our proof exploits its knapsack-like structure. However, we use the 2-dimensional knapsack problem in our analysis, instead of the standard knapsack problem.
The link to STACS 2012 is broken.
ReplyDeleteFixed. Thank you!
ReplyDeleteThank you!
ReplyDeleteYour post starts to make the following point without explicitly calling attention to it:
ReplyDeleteAbout 1 year ago, the Oveis Gharan-Saberi-Singh 1.5-eps approx appears on the Arxiv. Before it appears in print, the Momke-Svensson 1.461 approx appears on the Arxiv. Before it appears in print, the Mucha 1.444 approx is published on the Arxiv and the An-Kleinberg-Shmoys result for TSP Path appears on the Arxiv.
For all of these papers, the subsequent papers either explicitly build upon or are implicitly motivated by the preceding papers.
I think we can safely conclude that the Arxiv is helping to accelerate the pace of research.
Nick, you're right. The only obstacle to instantaneous research now is our ability to keep up!
ReplyDeleteThanks for the link Nick. I was looking for this info.
ReplyDelete