Optimization seminar

Modal title

Modal content

Autumn Semester 2019

Date / Time

Speaker

Title

Location

30 September 2019
16:30-17:30

Krzysztof Sornat
University of Wroclaw, Poland

Event Details

Optimization Seminar

Title	Approximation algorithms for generalizations of the k-Median clustering problem
Speaker, Affiliation	Krzysztof Sornat, University of Wroclaw, Poland
Date, Time	30 September 2019, 16:30-17:30
Location	HG G 19.1
Abstract	We consider generalizations of the k-Median clustering problem by applying a vector of weights to connection costs. In the Ordered k-Median problem the solution is evaluated by first sorting the client connection costs and then multiplying them with a predefined non-increasing weight vector (higher connection costs are taken with larger weights). Since the 1990s, this problem has been studied extensively in the discrete optimization and operations research communities and has emerged as a framework unifying many fundamental clustering and location problems such as k-Median and k-Center. Obtaining non-trivial approximation algorithms was an open problem even for simple topologies such as trees. Recently, Aouad and Segev [Math. Program. 2019] were able to obtain an O(log n)-approximation algorithm for Ordered k-Median using a sophisticated local-search approach. The existence of a constant-factor approximation algorithm, however, remained open even for the rectangular weight vector. In a joint work with Jaroslaw Byrka and Joachim Spoerhase [STOC 2018] we provide the first constant-factor approximation algorithm for the Ordered k-Median problem. Other generalization of k-Median is the OWA k-Median problem where clients are interested in having multiple facilities in their vicinity. In OWA k-Median we are given a non-increasing vector of weights and each client is served by all open facilities with connection costs scaled by the weights (higher connection costs are taken with smaller weights). In a joint work with Jaroslaw Byrka and Piotr Skowron [ICALP 2018] we provide an LP-rounding constant-factor approximation algorithm for the OWA k-Median problem with harmonic weights. To the best of our knowledge this is the first constant factor approximation algorithm for a variant of k-Median without assuming the triangle inequality. The algorithm we propose is based on dependent rounding [Srinivasan, FOCS 2001] applied to the solution of a natural LP-relaxation of the problem.

Approximation algorithms for generalizations of the k-Median clustering problemread_more

HG G 19.1

11 November 2019
16:30-17:30

Dr. Jakub Tarnawski
Microsoft Research, Zurich

Event Details

Optimization Seminar

Title	A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
Speaker, Affiliation	Dr. Jakub Tarnawski, Microsoft Research, Zurich
Date, Time	11 November 2019, 16:30-17:30
Location	HG G 19.1
Abstract	We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation. Our techniques build upon the constant-factor approximation algorithm for the special case of node-weighted metrics. Specifically, we give a generic reduction to structured instances that resemble but are more general than those arising from node-weighted metrics. For those instances, we then solve Local-Connectivity ATSP, a problem known to be equivalent (in terms of constant-factor approximation) to the asymmetric traveling salesman problem. This is joint work with Ola Svensson and László Végh.

A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problemread_more

HG G 19.1

18 November 2019
16:30-17:30

Dr. Vincent Cohen-Addad
Sorbonne Université, Paris, France

Event Details

Optimization Seminar

Title	From Local to Global: Local Search Algorithms Beyond the Worst-Case Analysis
Speaker, Affiliation	Dr. Vincent Cohen-Addad, Sorbonne Université, Paris, France
Date, Time	18 November 2019, 16:30-17:30
Location	HG G 19.1
Abstract	A classic problem in data analysis consists in partitioning the vertices of a network in such a way that vertices in the same set are densely connected. In practice, the most popular approaches rely on local search algorithms; not only for the ease of implementation and the efficiency, but also because of the accuracy of these methods on many real-world graphs. For example, the Louvain algorithm -- a local search based algorithm -- has quickly become the method of choice for detecting communities in social networks, accumulating more than 8600 citations over the past 10 years. However, explaining the success of these methods remains an open problem: in the worst-case, their performances can be arbitrarily bad. In this work, we study these local search heuristics and aim at explaining their success and identifying the mechanisms that make them successful through a classic model for social networks, the stochastic block model. We give the first theoretical evidence that Louvain finds the underlying natural partition of the network.

From Local to Global: Local Search Algorithms Beyond the Worst-Case Analysisread_more

HG G 19.1

25 November 2019
16:30-17:30

Felix Hommelsheim
TU Dortmund University, Dortmund, Germany

Event Details

Optimization Seminar

Title	Flexible Graph Connectivity: Approximating Network Design Problems Between 1- and 2-connectivity
Speaker, Affiliation	Felix Hommelsheim, TU Dortmund University, Dortmund, Germany
Date, Time	25 November 2019, 16:30-17:30
Location	HG G 19.1
Abstract	Graph connectivity and network design problems are among the most fundamental problems in combinatorial optimization. The minimum spanning tree problem, the two edge-connected spanning subgraph problem (2-ECSS) and the tree augmentation problem (TAP) are all examples of fundamental well-studied network design tasks that postulate different initial states of the network and different assumptions on the reliability of network components. In this paper we motivate and study Flexible Graph Connectivity (FGC), a problem that mixes together both the modeling power and the complexities of all aforementioned problems and more. In a nutshell, FGC asks to design a connected network, while allowing to specify different reliability levels for individual edges. While this non-uniform nature of the problem makes it appealing from the modeling perspective, it also renders most existing algorithmic tools for dealing with network design problems unfit for approximating FGC. In this paper we develop a general algorithmic approach for approximating FGC that yields approximation algorithms with ratios that are very close to the best known bounds for many special cases, such as 2-ECSS and TAP. Our algorithm and analysis combine various techniques including a weight-scaling algorithm, a charging argument that uses a variant of exchange bijections between spanning trees and a factor revealing non-linear optimization problem.

Flexible Graph Connectivity: Approximating Network Design Problems Between 1- and 2-connectivityread_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