AN ε-APPROXIMATION SCHEME FOR MINIMUM VARIANCE PROBLEMS

スポンサーリンク

概要

• 論文の詳細を見る

• Minimum variance problem may arise when we want to allocate a given amount of resource as fairly as possible to a finite set of activities under certain constraints. More formally, it is described as follows. Given a finite set E, a subset S of R^E and a function h_e(x(e)) from a certain domain to R for each e ∈ E (which represents the profit resulting from allocating x(e) amount of resource to activity e), the problem seeks to find x = {x(e) : e ∈ E} ∈ S that minimizes the variance of the vector {h_e(x(e)) : e ∈ E}. Here the variance of {h_e(x(e)) : e ∈ E} is defined as the summation over e ∈ E of the square of difference between the profit h_e(x(e)) and the mean value of profits of all activities. Such problem is called minimum variance problem This paper first presents a parametric characterization of optimal solutions. Based on this, for a class of problems satisfying certain assumptions, we shall develop an ε-approximation scheme which requires to solve the corresponding parametric problem a number of times polynomial in the input length and 1/ε. We shall then present three special cases for which such ε-approximation scheme becomes a fully polynomial time approximation scheme. The first case is that h_e is linear and increasing for each e, and the feasible set S is described by the set of linear equalities and/or inequalities containing the constraint such that the sum of x(e) over all e ∈ E is a fixed constant, and the second one is that h_e is linear and increasing for each e, and the feasible set S is the set of integral or real bases of submodular systems. The third one is that h_e is a certain nonlinear function and the feasible set S is the set of integral or real bases of a polymatroid. Finally we shall give a pseudopolynomial time algorithm if x(e) is an integer with lower and upper bounds on it, and the sum of x(e) over all e ∈ E is a fixed constant.

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

著者

• Katoh Naoki

  Department Of Architecture And Architectural Engineering Kyoto University

• Katoh Naoki

  Department Of Management Science Kobe University Of Commerce

関連論文

• 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

スポンサーリンク