Browsing ARC Theory Day by Title

Now showing items 4-5 of 5

    • A Randomized Rounding Approach for Symmetric TSP 

      Singh, Mohit (Georgia Institute of Technology, 2011-11-11)
      We show a (3/2-epsilon)-approximation algorithm for the graphical traveling salesman problem where the goal is to find a shortest tour in an unweighted graph G. This is a special case of the metric traveling salesman problem ...

    • Subexponential lower bounds for randomized pivoting rules for the simplex algorithm 

      Hansen, Thomas Dueholm (Georgia Institute of Technology, 2011-11-11)
      The simplex algorithm is among the most widely used algorithms for solving linear programs in practice. Most deterministic pivoting rules are known, however, to need an exponential number of steps to solve some linear ...