平成１１年度第１回KSMAP

第1回は組合せ最適化研究部会と合同で開催しました．

日時：５月１１日（火）　１４：３０ 〜 １７：００

場所：京都大学 物理系３１２講義室 
      京都大学へのアクセス
      会場へのアクセス

講演題目と講演者

『Approximating Fractional Multicommodity Flow Independent of the 
  Number of Commodities』
 Lisa K. Fleischer (Columbia University, NY, USA)

『Necessary Conditions for Solitaire Games Feasibility』
 Antoine Deza  (Tokyo Institute of Technology, Japan)

講演要旨：

Title: Approximating Fractional Multicommodity Flow Independent of the Number of Commodities

Speaker: Lisa K. Fleischer (Columbia University, NY, USA, and CORE, Universite' Catholique de Louvain, Belgium)

Abstract: Although fractional multicommodity flow problems can be solved in polynomial time via linear programming solution techniques, the problems are often quite large and can be quite difficult to solve exactly in practice. In many situations, approximate solutions suffice. For this reason, a number of researchers have proposed polynomial time approximation schemes for these problems, which have proven in practice to find approximate solutions an order of magnitude faster than approximate solutions obtained by LP methods. We review some of this work, describing fully polynomial time approximation schemes for various fractional multicommodity flow problems. We present the first approximation scheme for maximum multicommodity flow that is independent of the number of commodities k, and our algorithm improves upon the runtime of previous algorithms by this factor of k. For maximum concurrent flow, and minimum cost concurrent flow, we present algorithms that are faster than the current known algorithms when the graph is sparse or the number of commodities k is large, i.e. k > m/n (where m is the number of arcs and n is the number of nodes in the graph). Our algorithms are simple, deterministic, and for the versions without costs, they are strongly polynomial.

Title: Necessary Conditions for Solitaire Games Feasibility

Speaker: Antoine Deza (Tokyo Institute of Technology, Japan, and Centre d'Analyse et Mathematique Sociales, Paris, France)

Abstract: The classical game of Peg Solitaire has uncertain origins, but was certainly popular by the time of Louis XIV, and was described by Leibniz in 1710. The modern mathematical study of the game dates to the 1960s, when the solitaire cone was first described by Boardman and Conway. One of the classical problems concerning the peg solitaire game is the feasibility issue. Tools used to show the infeasibility of various peg games include valid inequalities over this cone, known as pagoda-functions, and the so-called rule-of-three. Here we introduce and study another necessary condition: the solitaire lattice criterion. While the lattice criterion is shown to be equivalent to the rule-of-three for the classical English 33-board and French 37-board as well as for any m by n board, the lattice criterion is stronger than the rule-of-three for games played on more complex boards. In fact, for a wide family of boards presented in this paper, the lattice criterion exponentially outperforms the rule-of-three. We also recall recent results on the extremal structure of solitaire cones and the link with the well studied metric cone such as an equivalence between the multicommodity flow problem (with associated dual metric cone) and a generalized peg game (with associated solitaire cone); a related NP-completeness result; a method of generating large classes of facets and exponential upper and lower bounds (in the dimension) on the number of facets.

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

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

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