平成１１年度第４回KSMAP

次回の研究会では, 京都大学の永持先生と, 現在京都大学に客員教授として日本に滞在中の Magnus M. Halldorsson 先生にご講演をお願いしました. お二人とも組合せ最適化アルゴリズムに対する理論的研究で大活躍なさっている先生方です. 皆様のご参加と活発なディスカッションを期待しております.

日時：９月８日（水）　１５：００ 〜 １７：３０

場所：京都大学  工学部８号館 共同２講義室

       京都大学へのアクセス

講演題目と講演者

  An Approximation for Finding a Smallest 2-Edge-Connected Subgraph
  Containing a Specified Spanning Tree
    永持 仁 (京都大学情報学研究科)

  Sum Coloring of Graphs
    Magnus M. Halldorsson (京都大学情報学研究科)

講演要旨：

An Approximation for Finding a Smallest 2-Edge-Connected Subgraph Containing a Specified Spanning Tree

永持仁 (京都大学情報学研究科)

Given a graph $G=(V,E)$ and a tree $T=(V,F)$ with $E\cap F=\emptyset$ such that $G+T=(V,F\cup E)$ is 2-edge-connected, we consider the problem of finding a smallest 2-edge-connected spanning subgraph $(V,F\cup E')$ of $G+T$ containing $T$. The problem, which is known to be NP-hard, admits a 2-approximation algorithm. However, obtaining a factor better than 2 for this problem has been one of the main open problems in the graph augmentation problem. In this talk, we show that the problem is $(\frac{51}{26}+\epsilon)$-approximable in $O(n^{1/2}m+n^{2})$ time for any constant $\epsilon>0$, where $n=|V|$ and $m=|E\cup F|$.

Sum Coloring of Graphs

Magnus M. Halldorsson (京都大学情報学研究科)

In this talk, we look at a family of graph coloring problems that were initially motivated by resource allocation in distributed systems, but have also applications to scheduling situations in other disparate fields. We are given a set of jobs with associated job lengths and a collection of pairwise conflicts, and want to find a cost-effective schedule of the jobs.
We can represent this as a graph multi-coloring problem, where each vertex is to receive as many colors as the length of the corresponding job. There are three variants: nonpreemptive schedule (where colors of a job must be contiguous), preemptive schedule, and unit-length jobs. The objective of the problem can either be to minimize the length of the schedule (chromatic number), or to minimize the sum of completion times of the jobs (chromatic sum). We focus on the latter objective that has received less attention.
We give an overview of the main results that have been obtained for these problems, and the way these results were obtained.

３２名の参加がありました．参加していただいた方々，どうもありがとうございました．

柳浦睦憲(yagiura@kuamp.kyoto-u.ac.jp)

<最終更新作成日時 1999年9月9日 >