[DMANET] CfP - Summer Lectures on Advanced Approximation Algorithms

Call for Participation - Summer Lectures on Advanced Approximation
Algorithms


======================

CALL FOR PARTICIPATION

Summer Lectures on Advanced Approximation Algorithms
Lecturer: Fabrizio Grandoni (IDSIA)
When: 16-20 June 2014
Where: Institute of Theoretical Computer Science, ETH Zürich, Switzerland
Website: http://pwgrp1.inf.ethz.ch/summerlectures14/

======================


ABSTRACT
Most optimization problems that we need to solve in practice turn out to
be NP-hard. The goal of approximation algorithms is to compute efficiently
an approximate solution to a NP-hard optimization problem.

In these lectures we will describe some of the most relevant and recent
results
and techniques in the area of approximation algorithms. We will study a few
fundamental problems, which appear in several real-world applications,
such as: vertex and set cover, independent and dominating set, knapsack
and bin packing, traveling salesman, Steiner tree and its
generalizations, k-center, facility location, maximum satisfiability and
many others.

Along the way, we will illustrate some common and powerful techniques in
the design and analysis of approximation algorithms: dynamic programming,
greedy heuristics, local search, randomized algorithms, LP rounding,
the primal-dual method, iterative rounding, etc.

We will also discuss the limits of approximation algorithms, by
presenting some approximation lower bounds and inapproximability
results.


ORGANIZATION

Prerequisites:
Familiarity with basic notions in probability theory, linear programming
and algorithm theory.
However, all the useful definitions and results will be summarized
during the lectures.

Target audience:
PhD Students and excellent Master students in Computer Science and
Mathematics.
Master students need to submit a Transcript of Records with their
application.

Duration:
Daily: 3 hours of lectures, before and after Lunch.
Assignments for students: Around the lectures; will be discussed daily.
At the end of the lectures there will be an exam.


FURTHER INFORMATION

Registration: To register, please fill in the registration form on the
website.
There is no participation fee, but registration is mandatory.

Venue:
The summer lectures will take place at ETH Zürich in the CAB building.
The full address is:
ETH Zürich, Department of Computer Science
Universitätstrasse 6
8006 Zürich
Switzerland

Accomodation:
Zürich and Switzerland are attractive tourist destinations,
hence it is better to book as early as possible.
There is no administrative or financial travel support available.
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************