代教的および確率的手法による離散構造の限界の究明

使用算术和概率方法研究离散结构的极限

基本信息

批准号：
16092205
负责人：
伊東利哉
金额：
$ 8.83万
依托单位：
Tokyo Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research on Priority Areas
财政年份：
2004
资助国家：
日本
起止时间：
2004 至 2007
项目状态：
已结题

项目摘要

本研究では、代数的手法および確率的手法を用いて、置換族の構成、電子商取引、 VLSI計算、可逆計算、および耐故障計算などに関する離散構造の限界を解明した、置換族の構成に関しては、電子文書間の高速な類似性ツールとして応用が知られているκ限定ε近似的最小値独立置換族Fに対して、一般分布上で定義される置換族Fを行列Uにより定式化し、その行列Uの階数を評価することにより置換族Fのサイズの良好な下界を導出した。電子商取引に関しては、最適選好マッチング問題において、顧客集合が複数の重み付きグループに分割されているとき、顧客数n商品数mの比に関して、乱択化最適選好マッチングが存在するためのほほ合致する上界と下界を導出した(これは、既に知られている顧客集合が1つグループである場合の乱択化最適選好マッチングが存在するための顧客数nと商品数mの比に関する上界・下界の拡張である)。まだ、商品価格設定問題に関しては、正価格モデルおよび無損失割引モデルにおいて見積価格が制限された場合に対して、確率的手法を用いることで,グラフ価格設定問題・線状高速道路問題・環状高速道路問題の良好な近似アルゴリズムを提案した。VLSI計算に関しては、3次元チャネル配線問題がNP困難であることを明らかにした。可逆計算に関しては、可逆回路の縮退故障に対する最小完全テスト集合生成問題がNP困難であることを示した。耐故障計算に関しては、様々なネットワークに対して効率的な確率的耐故障ネットワークを構成する統一的な手法を提案した。

在这项研究中，我们使用代数和随机方法来阐明取代基团，电子商务，VLSI计算，可逆计算和容错计算的离散结构的局限性。关于替代组的结构，我们使用矩阵u对κ限制ε近似最小值的最小值独立替代组F制定了替换组F，该基质均为矩阵U之间的电子文档中的快速相似性工具，并评估了矩阵u的最低限制的范围。匹配问题，当客户集分为多个加权组时，在存在一组已知的客户集时，存在随机最佳优先匹配的匹配上限和下界，以实现随机最佳优先匹配。尽管如此，就产品定价问题而言，对于图定价问题，线性高速公路问题和循环高速公路问题的良好近似算法是通过使用概率方法在公平价格模型和无损折扣模型中使用概率的。关于VLSI计算，据显示3D通道接线问题很难NP。关于可逆计算，已经表明，可逆电路退行性失败的最小完整测试集生成问题很困难。关于容错计算，提出了一种统一的方法来构建对各种网络有效的随机容错网络。