京都大学理学研究科の伊丹將人と申します。クロスポストご容赦ください。
京都大学非線形動力学分科佐々グループセミナーの案内をさせて頂きます。
奮ってご参加ください。
---佐々グループセミナー at 京都大学理学部---
講演者；高邉賢史（東京大学総合文化研究科福島研究室）
日時：2014年1月22日15:30-
場所：理学部5号館413号室
備考：セミナーは英語で行う予定です
Title:
Typical behavior of the linear programming method for combinatorial
optimization problems:
From a statistical-mechanical perspective
Abstract:
A linear programming problem (LP) is a popular class of optimization problem
s. It can be solved in polynomial time of the number N of variables while ot
her combinatorial optimization problems usually belong to a class of NP-hard
. We study typical behavior of the LP as a relaxation problem of the minimum
vertex cover problem which is a type of the integer programming problem (IP
). To deal with the LP and IP by statistical mechanics, a lattice-gas model
on the Erdos-Renyi random graphs including both problems as specific limits
in a model parameter is analyzed by a replica method. It is found that the L
P optimal solution is equal to that of the IP up to the highest order of N b
elow the critical average degree c*=e=2.71... as N→∞. The critical thresho
ld for LP=IP is beyond a mathematical result, c=1, predicted by a mathematic
al theorems for correspondence up to O(N). The threshold also coincides with
the replica-symmetry-breaking threshold of the IP. I would like to explain
details of our study and related topics.