课题基金 / 基金详情

A Systematic Approach to Network Approximation Algorithms with Performance Guarantees

A Systematic Approach to Network Approximation Algorithms with Performance Guarantees
具有性能保证的网络逼近算法的系统方法
批准号:
14580389
负责人:
ASANO Takao
金额:
$2.24万
依托单位:
依托单位国家:
日本
项目类别:
Grant-in-Aid for Scientific Research (C)
财政年份:
2002
资助国家:
日本
项目状态:
已结题
起止时间:
2002 至 2004

项目摘要

项目成果

ASANO Takao的其他基金

相似基金

相关文献

中文摘要
翻译
本研究的目的是从理论和实践的角度研究一种具有性能保证的网络逼近算法的系统方法,并阐明其对算法研究发展的有用性和约束,这对于本世纪的信息技术至关重要。为了实现这一目标,我们做了以下研究。我们对半定规划和线性规划技术进行了研究,这些技术被认为是设计和分析具有性能保证的网络逼近算法的潜在系统方法。更具体地说,我们通过翻译 V.V.Vazirani 撰写的《近似算法》一书以及 B.Korte 和 J.Vygen 撰写的《组合优化》一书来调查最近的趋势。这两本书被认为是描述世界上网络算法和逼近算法最新进展的最好的书。通过这次调查,我们获得了一些力量,并将这种力量应用于开发新的网络逼近算法。实际上,我们提出了MAX SAT当前最好的逼近算法。我们还提出了几种基于网络逼近算法的从Web上开发信息的算法。这些提出的算法发表在高标准的国际会议和期刊上。鉴于此,我们相信,本研究取得了令人满意的成果。
英文摘要
The objective of this research is to investigate a systematic approach to network approximation algorithms with performance guarantees from both theoretical and practical points of veiw and to clarify its usefulness and bound on the development of algorithmic researches which will be important for information technology in this centuary. To achive this objective, we have done the following researches.We made an investigation on semi-definite programming and linear programming techniques, which are considerd to be potential systematic approaches to designing and analyzing network approximation algorithms with performance guarantees.More specifically, we surveyed the recent trends by translating the book of Approximation Algorithms written by V.V.Vazirani and the book of Combinatorial Optimization written by B.Korte and J.Vygen. These two books are considered to be the best books describing the most recent progress in network algorithms and approximation algorithms in the world.Through this survey, we obtained some power and applied this power to developing new network approximation algorithms.Acutually, we proposed the current best approximation algorithm for MAX SAT.We also proposed several algorithms for exploiting inforamtion from the Web based on network approximation algorithms.These proposed algorithms were published in high standard international conferences and Journal.In view of this, we believe, the objective of this research is satisfactorily achieved.
期刊论文(60)
专著(0)
科研奖励(0)
会议论文
組合せ最適化(B.Korte and J.Vygen, Combinatorial Optimization, Springer, 2002の翻訳)
组合优化(B.Korte 和 J.Vygen 的翻译,组合优化,Springer,2002 年)
DOI: --
发表时间: 2005
期刊:
影响因子: --
作者: [浅野孝夫, 平田富夫, 小野孝男, 浅野泰仁]
通讯作者: 浅野泰仁
Takao Asano: "An Improved Analysis of Goemans and Williamson's LP-relaxation for MAX SAT"Proceedings of 14th Symposium on Foundamentals of Computation Theory. 14. 2-14 (2003)
Takao Asano:“Goemans 和 Williamsons LP-relaxation for MAX SAT 的改进分析”第 14 届计算理论基础研讨会论文集。
DOI: --
发表时间:
期刊:
影响因子: --
作者: []
通讯作者:
浅野 孝夫: "高性能近似アルゴリズムの設計と解析---線形計画緩和からのアプローチ"第15回RAMPシンポジウム論文集、日本オペレーションズ・リサーチ学会. 15. 86-103 (2003)
Takao Asano:“高性能近似算法的设计与分析——线性规划松弛的方法”第 15 届 RAMP 研讨会论文集,日本运筹学会 15. 86-103 (2003)。
DOI: --
发表时间:
期刊:
影响因子: --
作者: []
通讯作者:
DOI: --
发表时间: 2004
期刊: 中央大学理工学研究所論文集 9
影响因子: --
作者: [浅野孝夫, 九里史郎, 上ヶ原誠]
通讯作者: 上ヶ原誠
24
    Recursive Utility and Knightian Uncertainty: Theory and Applications
    • 批准号:
      23730299
    • 项目类别:
      Grant-in-Aid for Young Scientists (B)
    • 资助金额:
      $2.58万
    • 财政年份:
      2011
    • 负责人:
      ASANO Takao
    • 依托单位:
    Approximation algorithms for routing and scheduling problems on networks
    • 批准号:
      23500023
    • 项目类别:
      Grant-in-Aid for Scientific Research (C)
    • 资助金额:
      $3.24万
    • 财政年份:
      2011
    • 负责人:
      ASANO Takao
    • 依托单位:
    High-performance approximation algorithms for information-flow control problems on networks
    • 批准号:
      20500020
    • 项目类别:
      Grant-in-Aid for Scientific Research (C)
    • 资助金额:
      $2.91万
    • 财政年份:
      2008
    • 负责人:
      ASANO Takao
    • 依托单位:
    Real Option, Knightian Uncertainty and Applications
    • 批准号:
      20539005
    • 项目类别:
      Grant-in-Aid for Scientific Research (C)
    • 资助金额:
      $2.25万
    • 财政年份:
      2008
    • 负责人:
      ASANO Takao
    • 依托单位:
    海外基金