Papers accepted to SODA 2012

Recently the list of papers accepted to SODA 2012 has appeared. In it there is a paper on progress in TSP "A Proof of the Boyd-Carr Conjecture". According to its abstract, "Boyd and Carr [3] observe that we do not even know the worst-case upper bound on the ratio of the optimal 2-matching to the subtour LP; they conjecture the ratio is at most 10/9."

Making further Progress in Approximating graphic TSP

Another work concerning approximation of graphic TSP appeared recently. It improves analysis of Moemke and Svensson from $1.461$ to $1.458$ and makes it cleaner.

NP-complete problem which is neither NP-complete in the strong sense nor solvable by pseudopolynomial algorithms?

Recently I've posted on cstheory a question that is described in the title of this post. Since then I've received only one comment and one answer. I think the possible answer to it can be a list of NP-complete problems in the ordinary sense such that no pseudopolynomial algorithm is known for them.

Another approximation for Graphic TSP below 3/2

Today I've found out that T. Moemke and O. Svensson have made available on the net preprint "Approximating Graphic TSP by Matchings" with new approximation for Graphic TSP below 3/2. It should be mentioned that nearly 5 months ago there have appeared similar result: "A Randomized Rounding Approach to the Traveling Salesman Problem".

Multiobjective Optimization Complexity

Yesterday, there was uploaded an interesting paper on Multiobjective Optimization Complexity, called "The Complexity of Solving Multiobjective Optimization Problems and its Relation to Multivalued Functions". Authors of the paper describe results concerning complexity of different notions of "what it means to 'solve the problem'". For all this notions they define corresponding complexity classes and prove results on (non)equivalence of some of these new classes to such classes as $\mathbb{NP}$ or $\mathbb{NPMV}_g$, where $\mathbb{NPMV}_g$ is the complexity "class of multivalued functions whose graph is in $\mathbb{P}$".

People sometimes say “X is true.” A rule to discover if this statement makes any sense is ...

Though Richard Lipton wanted to tell eventually about that it's unknown whether Euclidean TSP is NP-complete/belongs to NP I liked the rule of his advisor:

People sometimes say “X is true.” A rule to discover if this statement makes any sense is to think about the statement: “X is false.” If the later is silly or obvious, then the original statement made no sense.

[1102.3766] Derandomizing HSSW Algorithm for 3-SAT

In their paper the authors write: "we obtain an $O(1.3303^n)$-time deterministic algorithm for 3-SAT, which is currently fastest."