AN EFFICIENT ALGORITHM FOR BICRITERIA MINIMUM-COST CIRCULATION PROBLEM

スポンサーリンク

概要

• 論文の詳細を見る

• This paper is concerned with a bicriteria minimum-cost circulation problem which arises in interactive multi criteria decision making. It presents a strongly polynomial algorithm for this problem, which runs in O(min{n^6 log^3 n, n^4(n log n + m) log^5 n}) time, where n and m are the numbers of vertices and edges in a graph respectively. It is achieved by making use of the parametric characterization of optimal solutions and a strongly polynomial algorithm for the single objective minimum-cost circulation problem. This idea is then extended to a minimum-cost circulation problem with one additional linear constraint and a strongly polynomial algorithm for this problem with the same running time is derived.

• 社団法人日本オペレーションズ・リサーチ学会の論文

著者

• Katoh N

  Kobe Univ. Commerce

• Katoh Naoki

  Department Of Architecture And Architectural Engineering Kyoto University

関連論文

• DS-1-7 無交差ラーマンフレームワーク列挙アルゴリズム(DS-1.COMP-NHC学生シンポジウム,シンポジウム)
• The Bacteriology of Acne Vulgaris and Antimicrobial Susceptibility of Propionibacterium acnes and Staphylococcus epidermidis Isolated from Acne Lesions
• 1B2 The Multicover Problem in Graphs arising from Patrol Route Planning
• An Efficient Algorithm for Evacuation Problem in Dynamic Network Flows with Uniform Arc Capacity(Invited Papers from New Horizons in Computing)
• AN EFFICIENT ALGORITHM FOR BICRITERIA MINIMUM-COST CIRCULATION PROBLEM
• Finding a Triangular Mesh with a Constant Number of Different Edge Lengths(Invited Papers from New Horizons in Computing)
• AN ε-APPROXIMATION SCHEME FOR MINIMUM VARIANCE PROBLEMS
• Online Vertex Exploration Problems in a Simple Polygon

スポンサーリンク