Department of Mathematics

Search

Optimization seminar

×

Modal title

Modal content

Autumn Semester 2018

Date / Time Speaker Title Location
22 October 2018
16:30-17:30 		Charalampos Angelidakis
ETH Zurich, Switzerland
Event Details

Optimization Seminar

Title Algorithmic and hardness results for the Hub Labeling problem
Speaker, Affiliation Charalampos Angelidakis, ETH Zurich, Switzerland
Date, Time 22 October 2018, 16:30-17:30
Location HG G 19.1
Abstract We will talk about the Hub Labeling problem, a preprocessing technique designed for speeding up shortest-path queries in graphs. Given an undirected graph G = (V, E) with edge lengths $l(e)$, $e \in E$, a Hub Labeling is a family of sets $H_u$, $u \in V$, such that for every pair {u,v}, the intersection $H_u \cap H_v$ contains a vertex lying on a shortest path between u and v. The main objective now is to compute a feasible Hub Labeling that minimizes the total size of the data structure produced, i.e. the sum $\sum_{u \in V} |H_u|$. In this talk, we present an $O(\log D)$-approximation algorithm for computing the minimum Hub Labeling on graphs with unique shortest paths and shortest-path diameter D; the unique shortest-paths property is a natural assumption when talking about real-life networks where edge lengths are obtained from (noisy) measurements. This result improves upon the $O(\log n)$-approximation algorithm by [Cohen et al `03] in various settings, e.g. for graphs with polylogarithmic shortest-path diameter. We complement this result with a strong hardness of approximation result on graphs with multiple shortest paths; we show that the problem is $\Omega(\log n)$-hard to approximate on graphs with multiple shortest paths, even when the shortest-path diameter is constant. We conclude with algorithms for computing a Hub Labeling on trees, and also demonstrate the equivalence of Hub Labeling on trees with a vertex search problem on trees that generalizes the standard binary search. Based on joint work with Yury Makarychev and Vsevolod Oparin.
Algorithmic and hardness results for the Hub Labeling problemread_more
HG G 19.1
26 November 2018
16:30-17:30 		Dr. Miriam Schloeter
ETH Zurich, Switzerland
Event Details

Optimization Seminar

Title Flows Over Time and Submodular Function Minimization
Speaker, Affiliation Dr. Miriam Schloeter, ETH Zurich, Switzerland
Date, Time 26 November 2018, 16:30-17:30
Location HG G 19.1
Abstract The main topic of my talk are two classical flow over time problems: the quickest transshipment problem and the earliest arrival transshipment problem. Given a network with capacities and transit times on the arcs and sources/sinks with supplies/demands, a quickest transshipment sends the supplies from the sources to meet the demands at the sinks as quickly as possible. Earliest arrival transshipments feature an additional property that is in particular desirable in the context of evacuation planning: an earliest arrival transshipment -- which in general only exists in networks with a single sink -- is a quickest transshipment maximizing the amount of flow that has reached the sinks for every point in time simultaneously. Both of these flow over time problems are deeply connected with certain submodular functions and minimizing these submodular functions seems to be central for efficiently computing quickest and earliest arrival transshipments: The algorithm of Hoppe and Tardos (1995) for solving the quickest transshipment problem and the algorithm of Baumann and Skutella (2006) for computing earliest arrival transshipments in networks with a single sink both heavily rely on repeated parametrized submodular function minimizations. The two algorithms also have in common that they use submodular function minimization only as a blackbox. Throughout my talk I will explain how exploiting the underlying algorithmic approach of submodular function minimization can be used to achieve multiple new results about the structure of quickest transshipments and earliest arrival transshipments (in networks with a single and also with multiple sinks) and their efficient computation. In particular, by opening up the blackbox of submodular function minimization, we are able to achieve algorithms for the quickest transshipment and the earliest arrival transshipment problem that significantly improv
Flows Over Time and Submodular Function Minimizationread_more
HG G 19.1
3 December 2018
16:30-17:30 		Felix Hommelsheim
TU Dortmund University, Dortmund, Germany
Event Details

Optimization Seminar

Title The Bulk-Robust Matching and Disjoint Path Problems
Speaker, Affiliation Felix Hommelsheim, TU Dortmund University, Dortmund, Germany
Date, Time 3 December 2018, 16:30-17:30
Location HG G 19.1
Abstract We consider the bulk-robust matching and disjoint path problems. In particular we are given a graph and a list of scenarios, each consisting of a set of edges that is deleted if the scenario materializes. The task for the bulk-robust matching problem is to compute a minimum-cost set of edges, that admits a perfect matching no matter which scenario arises. Similarly we define the bulk-robust disjoint path problem. We show that the bulk-robust bipartite matching problem is closely linked to the Directed Steiner Forest problem, even if each scenario consists of a single edge. We give approximation algorithms as well as exact algorithms for some graph classes. For the bulk-robust disjoint path problem we restrict our attention to a constant number of disjoint paths. Based on the work on the bulk-robust shortest path problem by Adjiashvili, Stiller and Zenklusen (2015) we present hardness results as well as approximation algorithms for different restrictions of the problem. Joint work with David Adjiashvili, Moritz Mühlenthaler and Oliver Schaudt.
The Bulk-Robust Matching and Disjoint Path Problemsread_more
HG G 19.1
10 December 2018
16:30-17:30 		Dr. Przemyslaw Uznanski
Institute of Theoretical Computer Science, ETH Zurich, Switzerland
Event Details

Optimization Seminar

Title A Framework for Searching in Graphs in the Presence of Errors
Speaker, Affiliation Dr. Przemyslaw Uznanski, Institute of Theoretical Computer Science, ETH Zurich, Switzerland
Date, Time 10 December 2018, 16:30-17:30
Location HG G 19.1
Abstract We consider a problem of searching for an unknown target vertex $t$ in a (possibly edge-weighted) graph. Each \emph{vertex-query} points to a vertex $v$ and the response either admits that $v$ is the target or provides any neighbour $s$ of $v$ that lies on a shortest path from $v$ to $t$. This model has been introduced for trees by Onak and Parys [FOCS 2006] and for general graphs by Emamjomeh-Zadeh et al. [STOC 2016]. In the latter, the authors provide algorithms for the error-less case and for the independent noise model (where each query independently receives an erroneous answer with known probability $p<1/2$ and a correct one with probability $1-p$). We study this problem both with adversarial errors and independent noise models. First, we show an algorithm that needs at most $\frac{\log_2 n}{1 - H(r)}$ queries in case of \emph{adversarial} errors, where the adversary is bounded with its rate of errors by a known constant $r<1/2$. Our algorithm is in fact a simplification of previous work, and our refinement lies in invoking an amortisation argument. We then show that our algorithm coupled with a Chernoff bound argument leads to a simpler algorithm for the independent noise model and has a query complexity that is both simpler and asymptotically better than the one of Emamjomeh-Zadeh et al. [STOC 2016]. Our approach has a wide range of applications. First, it improves and simplifies the Robust Interactive Learning framework proposed by Emamjomeh-Zadeh and Kempe [NIPS 2017]. Secondly, performing analogous analysis for \emph{edge-queries} (where a query to an edge $e$ returns its endpoint that is closer to the target) we actually recover (as a special case) a noisy binary search algorithm that is asymptotically optimal, matching the complexity of Feige et al. [SIAM J. Comput. 1994]. Thirdly, we improve and simplify upon an algorithm for searching of \emph{unbounded} domains due to Aslam and Dhagat [STOC 1991]. This is a joint work with D. Dereniowski, D. Graf and S. Tiegel, to be presented at SOSA@SODA 2019.
A Framework for Searching in Graphs in the Presence of Errorsread_more
HG G 19.1
17 December 2018
16:30-17:30 		Stephan Artmann
ETH Zurich, Switzerland
Christoph Glanzer
ETH Zurich, Switzerland
Event Details

Optimization Seminar

Title Strictly 3-modular matrices: Integer feasibility and flat directions
Speaker, Affiliation Stephan Artmann, ETH Zurich, Switzerland
Christoph Glanzer, ETH Zurich, Switzerland
Date, Time 17 December 2018, 16:30-17:30
Location HG G 19.1
Abstract An integral matrix A in m rows and n columns is strictly 3-modular if every n by n minor is in {-3,0,3}. We prove that for an inequality system associated with a strictly 3-modular matrix there is a polynomial-time algorithm to decide whether the system contains an integer point. Moreover, if the system does not contain an integer point, then regardless of the dimension of the underlying problem there exists a flat direction of width at most three that can be computed in polynomial-time. This is joint work with Robert Weismantel.
Strictly 3-modular matrices: Integer feasibility and flat directionsread_more
HG G 19.1

Note: if you want you can subscribe to the iCal/ics Calender.

Archive: SS 22 SS 20 AS 19 SS 19 AS 18 SS 18 AS 17 SS 17 AS 16 SS 16 AS 15 SS 15 AS 14 SS 14 AS 13 SS 13 AS 12 SS 12 AS 11 SS 11 AS 10 SS 10 AS 09

JavaScript has been disabled in your browser