[Turkmath:6693] Istanbul Ayrik Matematik Toplantilari Seminer Duyurusu Hatirlatmasi

[Türker BIYIKOĞLU]

Istanbul Ayrik Matematik Toplantilari Seminer Duyurusu Hatirlatmasi

Degerli Matematikciler,

Istanbul Ayrik Matematik Toplantilarinin ikincisi herzaman oldugu gibi 
Istanbul Matematiksel Bilimler Merkezinin (IMBM) cok guzel binasinda 
olucak.
Bu yilki son toplantimizda 4 Aralik Cuma gunu saat 11.00'de
Tuğkan Batu (London School of Economics, UK)  "Introduction to 
Aproximation Algorithms"
baslikli bir konusma yapacaktir.
Konusma konusuyla ilgili detaylari asagida ve ekteki ilanda gorebilirsiniz.

Seminer oncesi, saat 10.30'dan itibaren cay-kahve ve kurabiye servisi 
olacaktir. Konusmaya herkes davetlidir.

Turker Biyikoglu  Tinaz Ekim-Asici


I M B M istanbul center for mathematical sciences
Istanbul Discrete Mathematics Meetings

Introduction to Aproximation Algorithms
Tuğkan Batu
London School of Economics, UK

Abstract
In the first part of my talk, I will present a brief introduction to 
approximation
algorithms. In addition to introducing some fundamental notions and 
examples
from the topic, I will try to visit a few of the common techniques used 
in the design
of approximation algorithms.
In the second part of my talk, I will describe a sublinear-time asymptotic
approximation scheme for the bin packing problem. The bin packing 
problem is defined
as follows: given a set of n items with sizes 0 < w_1,...,w_n<=1, find a 
packing
of these items into minimum number of unit-size bins possible. I will 
present an
algorithm A_epsilon for any epsilon> 0, that has sampling access to the 
input instance and
outputs a value k such that Copt <= k <=   (1 + epsilon) 
Copt + 1, 
where Copt is the cost of
an optimal solution. (The second part of the talk is based on a joint 
publication
with Petra Berenbrink and Christian Sohler.)

Date: Friday, December 4, 2009
Time: 11:00
Place: IMBM Seminar Room, Bogazici University

Istanbul Matematiksel Bilimler Merkezinin hakkinda bilgi icin: 
http://imbm.org.tr/


-------------- sonraki bölüm --------------
Yazı olmayan bir eklenti temizlendi...
İsim: tugkan-batu.pdf
Tür: application/pdf
Boyut: 52535 bayt
Tanım: kullanılamıyor
Url: http://yunus.listweb.bilkent.edu.tr/pipermail/turkmath/attachments/20091202/6363f5c0/attachment-0001.pdf