ARC Theory DayThursday, November 10, 2011 and Friday, November 11, 2011http://hdl.handle.net/1853/450362019-06-17T06:49:09Z2019-06-17T06:49:09ZOnline algorithms and the k-server conjectureMadry, Aleksanderhttp://hdl.handle.net/1853/420272017-08-01T07:00:21Z2011-11-11T00:00:00ZOnline algorithms and the k-server conjecture
Madry, Aleksander
Traditionally, in the problems considered in optimization, one needs to produce the solution only after the whole input is made available. However, in many real-world scenarios the input is revealed gradually, and one needs to make irrevocable decisions along the way while having only partial information on the whole input. This motivates us to develop models that allow us to address such Scenarios. In this talk, I will consider one of the most popular approaches to dealing with uncertainty in optimization: the online model and competitive analysis; and focus on a central problem in this area: the k-server problem. This problem captures many online scenarios - in particular, the widely studied caching problem - and is considered by many to be the "holy grail" problem of the field. I will present a new randomized algorithm for the k-server problem that is the first online algorithm for this problem that achieves polylogarithmic competitiveness. Based on joint work with Nikhil Bansal, Niv Buchbinder, and Joseph (Seffi) Naor.
Presented on November 11, 2011 in Klaus 1116; Runtime: 50:25 minutes
2011-11-11T00:00:00ZMadry, AleksanderTraditionally, in the problems considered in optimization, one needs to produce the solution only after the whole input is made available. However, in many real-world scenarios the input is revealed gradually, and one needs to make irrevocable decisions along the way while having only partial information on the whole input. This motivates us to develop models that allow us to address such Scenarios. In this talk, I will consider one of the most popular approaches to dealing with uncertainty in optimization: the online model and competitive analysis; and focus on a central problem in this area: the k-server problem. This problem captures many online scenarios - in particular, the widely studied caching problem - and is considered by many to be the "holy grail" problem of the field. I will present a new randomized algorithm for the k-server problem that is the first online algorithm for this problem that achieves polylogarithmic competitiveness. Based on joint work with Nikhil Bansal, Niv Buchbinder, and Joseph (Seffi) Naor.A Randomized Rounding Approach for Symmetric TSPSingh, Mohithttp://hdl.handle.net/1853/420282017-08-01T07:00:20Z2011-11-11T00:00:00ZA Randomized Rounding Approach for Symmetric TSP
Singh, Mohit
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 when the underlying metric is defined by shortest path distances in G. The result improves on the 3/2-approximation algorithm due to Christofides for the case of graphical TSP. Similar to Christofides, our algorithm first finds a spanning tree whose cost is upper-bounded by the optimum and then it finds the minimum cost Eulerian augmentation of that tree. The main difference is in the selection of the spanning tree. Except in certain cases where the solution of LP is nearly integral, we select the spanning tree randomly by sampling from a maximum entropy distribution defined by the linear programming relaxation. Despite the simplicity of the algorithm, the analysis builds on a variety of ideas such as properties of strong Rayleigh measures from probability theory, graph theoretical results on the structure of near minimum cuts, and the integrality of the T-join polytope from polyhedral theory. This is joint work with Shayan Oveis Gharan and Amin Saberi.
Presented on November 11, 2011 in Klaus 1116; Runtime: 54:36 minutes
2011-11-11T00:00:00ZSingh, MohitWe 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 when the underlying metric is defined by shortest path distances in G. The result improves on the 3/2-approximation algorithm due to Christofides for the case of graphical TSP. Similar to Christofides, our algorithm first finds a spanning tree whose cost is upper-bounded by the optimum and then it finds the minimum cost Eulerian augmentation of that tree. The main difference is in the selection of the spanning tree. Except in certain cases where the solution of LP is nearly integral, we select the spanning tree randomly by sampling from a maximum entropy distribution defined by the linear programming relaxation. Despite the simplicity of the algorithm, the analysis builds on a variety of ideas such as properties of strong Rayleigh measures from probability theory, graph theoretical results on the structure of near minimum cuts, and the integrality of the T-join polytope from polyhedral theory. This is joint work with Shayan Oveis Gharan and Amin Saberi.Algorithms for Circuits and Circuits for AlgorithmsWilliams, Ryanhttp://hdl.handle.net/1853/420292017-08-01T07:00:17Z2011-11-11T00:00:00ZAlgorithms for Circuits and Circuits for Algorithms
Williams, Ryan
Connections have been recently developed between the existence of non-trivial circuitanalysis algorithms and proofs of circuit size lower bounds. Algorithms that can check whether a given circuit from some class satisfies a simple property (such as computing the all-zeroes function) can be used to prove limitations on that circuit class, provided the algorithms run slightly faster than exhaustive search. More precisely, a non-trivial SAT algorithm for a circuit class can be used to find functions computable in nondeterministic exponential time that cannot be computed by that circuit class. Informally, this connection can be interpreted as saying "good algorithms for circuits imply there are no good circuits for some algorithms." This talk will explore the ideas behind this theme and the potential for further progress.
Presented on November 11, 2011 in Klaus 1116; Runtime: 53:10 minutes
2011-11-11T00:00:00ZWilliams, RyanConnections have been recently developed between the existence of non-trivial circuitanalysis algorithms and proofs of circuit size lower bounds. Algorithms that can check whether a given circuit from some class satisfies a simple property (such as computing the all-zeroes function) can be used to prove limitations on that circuit class, provided the algorithms run slightly faster than exhaustive search. More precisely, a non-trivial SAT algorithm for a circuit class can be used to find functions computable in nondeterministic exponential time that cannot be computed by that circuit class. Informally, this connection can be interpreted as saying "good algorithms for circuits imply there are no good circuits for some algorithms." This talk will explore the ideas behind this theme and the potential for further progress.Subexponential lower bounds for randomized pivoting rules for the simplex algorithmHansen, Thomas Dueholmhttp://hdl.handle.net/1853/420262017-08-01T07:00:21Z2011-11-11T00:00:00ZSubexponential lower bounds for randomized pivoting rules for the simplex algorithm
Hansen, Thomas Dueholm
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 programs (Klee-Minty examples). No non-polynomial lower bounds on the expected number of steps were known, prior to this work, for randomized pivoting rules. We provide the first subexponential (i.e., of the form 2^(Omega(n^alpha)), for some alpha>0) lower bounds for the two most natural, and most studied, randomized pivoting rules suggested to date. Joint work with Oliver Friedmann and Uri Zwick.
Presented on November 11, 2011 in Klaus 1116; Runtime: 62:08 minutes
2011-11-11T00:00:00ZHansen, Thomas DueholmThe 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 programs (Klee-Minty examples). No non-polynomial lower bounds on the expected number of steps were known, prior to this work, for randomized pivoting rules. We provide the first subexponential (i.e., of the form 2^(Omega(n^alpha)), for some alpha>0) lower bounds for the two most natural, and most studied, randomized pivoting rules suggested to date. Joint work with Oliver Friedmann and Uri Zwick.