| 発表言語 |
日本語
|
| 開催日 |
2011年04月27日 16時30分
|
| 終了日 |
2011年04月27日 17時30分
|
| 開催場所 | 京都大学数理解析研究所110号室 |
| セミナー名 | 談話会 |
| タイトル |
A bound for the 2-edge-connected subgraph problem |
| 分野 |
代数
幾何
解析
その他
|
| 講演者名 | Ramamoorthi Ravi |
| 講演者所属 | 京大・数理研 & Tepper School of Business, Carnegie Mellon University |
| 概要 | The minimum-cost traveling salesperson problem (TSP) that asks for
a shortest Hamiltonian circuit is perhaps the most studied problem
in combinatorial optimization. Since it is NP-complete, finding
good approximation algorithms is an important area of study. A
longstanding open problem in this direction concerns the metric
version where the costs obey the triangle inequality. In this case,
it has been widely conjectured that a shortest Hamilton circuit has
cost at most four-thirds the value of the subtour linear
programming (LP) relaxation. In the metric case, this LP relaxation
coincides with the LP relaxation for finding a minimum-cost
two-edge-connected subgraph.
The simplest fractional solutions to the subtour LP relaxation are
half integral solutions where every edge variable is a multiple of
half. We show that the minimum cost of a 2-edge-connected subgraph
is at most four-thirds that of the minimum cost half-integral
solution of the subtour relaxation, lending support to the
conjecture.
This talk describes joint work with Robert Carr from Sandia
National Laboratories.
|
| 備考 | ◆ 多数のご来聴をお待ちしております．
◆ とくに院生の出席を歓迎します． |
| リンク | http://www.kurims.kyoto-u.ac.jp/ja/seminar/danwakai.html |