{"id":51,"date":"2016-09-27T10:41:09","date_gmt":"2016-09-27T13:41:09","guid":{"rendered":"http:\/\/eventos.cmm.uchile.cl\/discretas2017\/?page_id=51"},"modified":"2016-12-26T13:46:34","modified_gmt":"2016-12-26T16:46:34","slug":"cursos","status":"publish","type":"page","link":"https:\/\/eventos.cmm.uchile.cl\/discretas2017\/cursos\/","title":{"rendered":"Cursos"},"content":{"rendered":"

\u201cAlgorithms for Network Flows\u201d<\/strong><\/h3>\n
Neil Olver<\/a>
\nVrije Universiteit Amsterdam and CWI.<\/h6>\n
Abstract:<\/h6>\n

\u00bb In this series of lectures, we will discuss algorithms for maximum
\nflow, minimum cost flow, and generalized flow (where flow is scaled as
\nit traverses arcs). Flow problems are amongst the most important in
\ncombinatorial optimization, and there is a huge body of literature on
\nthe topic. We will focus on combinatorial algorithms, and especially
\nstrongly polynomial algorithms. This means that the number of
\narithmetic operations depend only on the size of the network, and not
\non the sizes of the numbers used to encode capacities and costs. While
\nmany of the algorithms we will discuss are quite classical, we will
\nwork towards very recent results on strongly polynomial algorithms for
\ngeneralized flow maximization.\u00bb<\/span><\/p>\n

 <\/p>\n

\u201cApproximation algorithms for the traveling salesman problem (and related recent advances) \u201c<\/strong><\/h3>\n
David Shmoys <\/a>
\nCornell University, USA.<\/h6>\n
Abstract:<\/h6>\n
\u00abWe will survey a number of recent results that yield improved approximation algorithms for variants of the traveling salesman problem (TSP); an\u00a0r<\/i>-approximation algorithm for an optimization is a polynomial-time algorithm that is guaranteed to find a feasible solution of objective function value within a factor of\u00a0r<\/i>\u00a0of optimal. The common unifying theme throughout these lectures will be the role of randomization and linear programming in advancing the state of the art in this area over the past five years.\u00a0<\/span><\/span>We shall briefly discuss recent results of Oveis Gharan, Saberi, & Singh and M\u00f6mke & Svensson for the graphical TSP, as well as the result of Asadpour, Goemans, M\u0105dry, Oveis Gharan, & Saberi for the asymmetric TSP in greater detail. We shall focus next on results for the\u00a0<\/span>s<\/i>–t<\/i>\u00a0path traveling salesman problem.\u00a0\u00a0In the\u00a0s<\/i>–t<\/i>\u00a0path TSP, we are given pairwise distances among\u00a0n<\/i>\u00a0points that satisfy the triangle inequality, and two specified endpoints\u00a0s<\/i>\u00a0and\u00a0t<\/i>; the problem is to find a shortest Hamiltonian path between\u00a0s<\/i>\u00a0and\u00a0t<\/i>. Hoogeveen showed that the natural variant of the classic TSP algorithm of Christofides is a 5\/3-approximation algorithm for this problem, and this asymptotically tight bound in fact has been the best approximation ratio known until now. We shall present a result of An, Kleinberg, and Shmoys, which provides an approximation algorithm that is guaranteed to find a solution of cost within a factor of the golden ratio of optimal in polynomial time for any metric input. This result is based on modifying Christofides’ algorithm so that it randomly chooses the initial spanning tree based on an optimal solution to a natural linear programming relaxation, rather than a minimum spanning tree; this simple but crucial modification leads to an improved approximation ratio, surpassing the 20-year-old barrier set by the natural Christofides’ algorithm variant. We shall discuss a number of subsequent improvements, first by Seb\u0151, who gives a refinement of this approach that yields a 1.6-approximation algorithm. We present an elegant result of Gao, that provides a much simpler approach to match a result of Seb\u0151 and Vygen that gives a 1.5-approximation algorithm for the graphical metric case of this problem. Finally, we briefly outline the most recent improvements made by\u00a0Gottschalk & Vygen, and by\u00a0Seb\u0151\u00a0& Van Zuylen.\u00bb<\/div>\n

<\/h3>\n

\u201cComputing the Volume in High Dimension\u201d (en espa\u00f1ol)
\n<\/strong><\/h3>\n
Santosh Vempala<\/a>
\nGeorgia Tech, USA.<\/h6>\n
Abstract:<\/h6>\n

\u00abEl problema del c\u00e1lculo del volumen en dimensi\u00f3n alta es un problema\u00a0antiguo, b\u00e1sico y dif\u00edcil.\u00a0 Esta muy conectado con los problemas de\u00a0optimizaci\u00f3n, aprendizaje y muestreo al azar. En las ultimas tres \u00a0d\u00e9cadas, la investigaci\u00f3n de algoritmos para calcular el volumen ha\u00a0resultado en t\u00e9cnicas profundas para algoritmos en general y tambi\u00e9n
\npara las matem\u00e1ticas de dimensi\u00f3n alta. Este curso tiene cuatro partes:<\/p>\n

(1) introducci\u00f3n a los problemas, el modelo y la estructura de objetos
\nconvexos.<\/p>\n

(2) Algoritmos y reducciones<\/p>\n

(3) Geometr\u00eda Convexa asint\u00f3tica y<\/p>\n

(4) Paseos aleatorios geom\u00e9tricos y sus an\u00e1lisis.\u00bb<\/p>\n

 <\/p>\n

 <\/p>\n","protected":false},"excerpt":{"rendered":"

\u201cAlgorithms for Network Flows\u201d Neil Olver Vrije Universiteit Amsterdam and CWI. Abstract: \u00bb In this series of lectures, we will discuss algorithms for maximum flow, minimum cost flow, and generalized flow (where flow is scaled as it traverses arcs). Flow problems are amongst the most important in combinatorial optimization, and there is a huge body … Seguir leyendo Cursos<\/span> →<\/span><\/a><\/p>\n","protected":false},"author":31,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"inline_featured_image":false,"footnotes":""},"class_list":["post-51","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2017\/wp-json\/wp\/v2\/pages\/51","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2017\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2017\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2017\/wp-json\/wp\/v2\/users\/31"}],"replies":[{"embeddable":true,"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2017\/wp-json\/wp\/v2\/comments?post=51"}],"version-history":[{"count":6,"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2017\/wp-json\/wp\/v2\/pages\/51\/revisions"}],"predecessor-version":[{"id":73,"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2017\/wp-json\/wp\/v2\/pages\/51\/revisions\/73"}],"wp:attachment":[{"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2017\/wp-json\/wp\/v2\/media?parent=51"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}