Further talks

Modal title

Modal content

Spring Semester 2019

Date / Time

Speaker

Title

Location

28 January 2019
16:30-17:30

Paccagnan Dario
Automatic Control Laboratory of ETH Zurich

Details

IFOR talks

Title	Generalized coverage problems: approximation through game design
Speaker, Affiliation	Paccagnan Dario, Automatic Control Laboratory of ETH Zurich
Date, Time	28 January 2019, 16:30-17:30
Location	HG G 19.1
Abstract	In this talk we show how game theory can be leveraged to provide near optimal solutions to a class of intractable combinatorial problems termed general multi-agent maximum coverage problems (GMMC). In a GMMC problem we are given a ground set of elements, and n collections of subsets of the ground set. Each element in the ground set is associated with a value. The goal is to select one subset from each collection so as to maximize the value of covered elements, weighted by a function that depends on how many times each element is included in the chosen subsets. In the game-theoretic setting considered, we let each agent select a set from each collection and reward him with a corresponding utility function. In this talk we ask the following two questions. Given agents' utility functions, how do we characterize the performance of the worst-case Nash equilibrium? Is it possible to design utility functions so as to maximize such performance metric? Our main result is that both the problems of characterizing and optimizing the equilibrium performance can be reformulated as tractable linear programs. We specialize these results to the case of submodular and supermodular maximization problems. Relative to the class of submodular maximization problems subject to matroid constraints, we show that optimally-designed utilities yield an improved approximation ratio compared to the state of the art algorithms.

Generalized coverage problems: approximation through game designread_more

HG G 19.1

14 February 2019
14:00-15:00

Prof. Dr. Jens Vygen
University of Bonn, Bonn, Germany

Details

IFOR talks

Title	Resource Sharing, Routing, Chip-Design
Speaker, Affiliation	Prof. Dr. Jens Vygen, University of Bonn, Bonn, Germany
Date, Time	14 February 2019, 14:00-15:00
Location	HG G 19.1
Abstract	Chip design is one of the most fascinating application areas of mathematics. After a brief overview we focus on routing, a key problem. The task is to interconnect millions of sets of pins by disjoint wires. This is difficult because (a) instance sizes are huge (graphs with billions of vertices), (b) resources such as space and propagation time are very limited, and (c) even the simplest special cases are NP-hard. We show how to model routing by a very abstract problem, known as min-max resource sharing. This includes a novel way of modeling timing constraints. Our simple combinatorial fully polynomial approximation scheme is both faster and more general than previous algorithms. In practice we solve huge instances nearly optimally. Our overall router, BonnRoute, is far superior to commercial routing tools and has been used for designing many of the most challenging chips. This is based on joint work with Stephan Held, Dirk Müller, Klaus Radke, Daniel Rotter, Pietro Saccardi, Rudolf Scheifele, Vera Traub, and others.

Resource Sharing, Routing, Chip-Designread_more

HG G 19.1

15 February 2019
10:00-11:00

Vera Traub
hcm Hausdorff Center for Mathematics, Bonn, Germany

Details

IFOR talks

Title	Beating the integrality ratio for s-t-tours in graphs
Speaker, Affiliation	Vera Traub, hcm Hausdorff Center for Mathematics, Bonn, Germany
Date, Time	15 February 2019, 10:00-11:00
Location	HG G 19.1
Abstract	The s-t-path TSP is the variant of the traveling salesman problem in which the endpoints of the tour are given and distinct. In this talk we consider the important special case of the s-t-path TSP in unit weight graphs, the s-t-path graph TSP. Among various variants of the traveling salesman problem, the s-t-path graph TSP has the special feature that we know the exact integrality ratio, 3/2, and an approximation algorithm matching this ratio. In this work, we go below this threshold: we devise a polynomial-time algorithm for the s-t-path graph TSP with approximation ratio 1.497. Our algorithm can be viewed as a refinement of the 3/2-approximation algorithm by Sebő and Vygen [2014], but we introduce several completely new techniques. These include a new type of ear-decomposition, an enhanced ear induction that reveals a novel connection to matroid union, a stronger lower bound, and a reduction of general instances to instances in which s and t have small distance (which works for general metrics). This is joint work with Jens Vygen.

Beating the integrality ratio for s-t-tours in graphsread_more

HG G 19.1

3 June 2019
16:00-18:00

Dr. Victor Verdugo
London School of Economics and Political Science, London, UK

Details

IFOR talks

Title	A 4-competitive algorithm for the graphic secretary problem
Speaker, Affiliation	Dr. Victor Verdugo, London School of Economics and Political Science, London, UK
Date, Time	3 June 2019, 16:00-18:00
Location	HG G 26.1

A 4-competitive algorithm for the graphic secretary problem

HG G 26.1

Notes: wenn Sie möchten, können Sie den iCal/ics-Kalender abonnieren.

Archive: undefined undefined undefined undefined undefined undefined undefined undefined undefined undefined undefined undefined undefined