We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of…
Is matching in NC, i.e., is there a deterministic fast parallel algorithm for it? This has been an outstanding open question in TCS for over three decades, ever since the discovery of Random NC matching…
Our results are: ** Introduce the problem of finding stable matchings that are robust to errors in the input. ** An efficient algorithm for the following class of errors: Permute arbitrarily the preference list of…
Microsoft is a Silver sponsor of the Federated Logic Conference 2018 (FLoC 2018) July 6–9, 2018 at a variety of venues in Oxford, UK.
Common-sense physical reasoning is facilitated by representing sensory percepts into discrete objects. By decomposing a complex visual scene into distinct objects, humans can describe relations between the objects and reason about their dynamics as well…
