Amin Saberi
Constant factor approximation to the bounded genus instances of ATSP.
Ср, 09/16/2009 - 13:16 — SomNambulAuthors: Amin Saberi, Shayan Oveis Gharan
Subjects: Data Structures and Algorithms
AbstractWe give a constant factor approximation algorithm for the asymmetric
traveling salesman problem when the underlying undirected graph of the
Held-Karp linear programming relaxation of the problem has orientable bounded
genus. Our result also implies the weak version Goddyn's conjecture on the
existence of thin trees on graphs with orientable bounded genus.Maximizing Stochastic Monotone Submodular Functions.
Чт, 08/20/2009 - 23:06 — SomNambulAuthors: Arash Asadpour, Hamid Nazerzadeh, Amin Saberi
Subjects: Optimization and Control
AbstractWe study the problem of maximizing a stochastic monotone submodular function
with respect to a matroid constraint. We study the adaptivity gap - the ratio
between the values of optimal adaptive and non-adaptive policies - and show
that it is equal to e/(e-1). This result implies that the benefit of adaptivity
is bounded. We also study the myopic policy and show that it is a
1/2-approximation. Furthermore, when the matroid is uniform, approximation
ratio of the myopic policy becomes 1-1/e which is optimum.
Вход в систему
