論文の概要: Function Design for Improved Competitive Ratio in Online Resource
Allocation with Procurement Costs
- arxiv url: http://arxiv.org/abs/2012.12457v1
- Date: Wed, 23 Dec 2020 02:32:47 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-25 18:16:15.700016
- Title: Function Design for Improved Competitive Ratio in Online Resource
Allocation with Procurement Costs
- Title(参考訳): 調達コストを考慮したオンライン資源配分における競争率向上のための機能設計
- Authors: Mitas Ray, Omid Sadeghi, Lillian J. Ratliff, Maryam Fazel
- Abstract要約: 私たちは、複数の顧客が到着するオンラインリソースアロケーションの問題を研究し、売り手は、合計アロケーションのための調達コストに直面しながら、各受信顧客にリソースを割り当てなければなりません。
- 参考スコア(独自算出の注目度): 16.68130648568593
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of online resource allocation, where multiple customers
arrive sequentially and the seller must irrevocably allocate resources to each
incoming customer while also facing a procurement cost for the total
allocation. Assuming resource procurement follows an a priori known marginally
increasing cost function, the objective is to maximize the reward obtained from
fulfilling the customers' requests sans the cumulative procurement cost. We
analyze the competitive ratio of a primal-dual algorithm in this setting, and
develop an optimization framework for synthesizing a surrogate function for the
procurement cost function to be used by the algorithm, in order to improve the
competitive ratio of the primal-dual algorithm. Our first design method focuses
on polynomial procurement cost functions and uses the optimal surrogate
function to provide a more refined bound than the state of the art. Our second
design method uses quasiconvex optimization to find optimal design parameters
for a general class of procurement cost functions. Numerical examples are used
to illustrate the design techniques. We conclude by extending the analysis to
devise a posted pricing mechanism in which the algorithm does not require the
customers' preferences to be revealed.
- Abstract(参考訳): 我々は、複数の顧客が順次到着し、売り手が入ってくる各顧客に対して無意味にリソースを割り当てると同時に、総割り当ての調達コストに直面するオンラインリソース割り当ての問題について検討する。
資源調達が限界的に増大するコスト関数に従えば、顧客の要求を満たすことで得られる報酬が累積調達コストに匹敵する最大化が目的である。
本研究では,本手法におけるプライマル・デュアルアルゴリズムの競合比を分析し,アルゴリズムが使用する調達コスト関数のサロゲート関数を合成する最適化フレームワークを開発し,プライマル・デュアルアルゴリズムの競合比を向上させる。
最初の設計手法は, 多項式調達コスト関数に着目し, 最適サロゲート関数を用いて, より洗練された境界を提供する。
第2の設計手法は, 準凸最適化を用いて, 調達コスト関数の一般クラスに対する最適設計パラメータを求める。
数値的な例は設計技法を説明するために使われる。
分析を拡張して、アルゴリズムが顧客の好みを明らかにする必要のない価格設定メカニズムを考案する。
関連論文リスト
- Rethinking and Benchmarking Predict-then-Optimize Paradigm for
Combinatorial Optimization Problems [62.25108152764568]
多くのWebアプリケーションは、エネルギーコストを考慮したスケジューリング、Web広告の予算配分、ソーシャルネットワークでのグラフマッチングなど、最適化問題の解決に頼っている。
統一システムにおける予測と意思決定の性能について考察する。
我々は、現在のアプローチを包括的に分類し、既存の実験シナリオを統合する。
論文 参考訳(メタデータ) (2023-11-13T13:19:34Z) - Refined Mechanism Design for Approximately Structured Priors via Active
Regression [50.71772232237571]
我々は、大量の商品を戦略的入札者に販売する収益を最大化する販売業者の問題を考える。
この設定の最適かつほぼ最適のメカニズムは、特徴付けや計算が難しいことで有名である。
論文 参考訳(メタデータ) (2023-10-11T20:34:17Z) - Approaching Collateral Optimization for NISQ and Quantum-Inspired
Computing [0.0]
担保最適化(Collateral optimization)とは、債務又は担保取引を満たすための金融資産の体系的な配分を指す。
一般的な目的の1つは、特定のトランザクションや取引ポートフォリオに関連するリスクを軽減するのに必要な担保コストを最小限にすることである。
論文 参考訳(メタデータ) (2023-05-25T18:01:04Z) - Multi-objective robust optimization using adaptive surrogate models for
problems with mixed continuous-categorical parameters [0.0]
ロバスト設計の最適化は、不確実性が主に目的関数に影響を与える場合、伝統的に考慮されている。
結果として生じるネスト最適化問題は、非支配的ソート遺伝的アルゴリズム(NSGA-II)において、汎用的な解法を用いて解決することができる。
提案手法は、適応的に構築されたKrigingモデルを用いて、NSGA-IIを順次実行し、量子を推定する。
論文 参考訳(メタデータ) (2022-03-03T20:23:18Z) - Online Learning with Knapsacks: the Best of Both Worlds [54.28273783164608]
オンライン学習の課題として,意思決定者が,リソース制約の有限セットに違反することなく,期待する報酬を最大化したい,という課題を提起する。
当社のフレームワークは,意思決定者がそのエビデンスを柔軟かつコスト論的に扱えるようにします。
論文 参考訳(メタデータ) (2022-02-28T12:10:48Z) - Multi-Step Budgeted Bayesian Optimization with Unknown Evaluation Costs [28.254408148839644]
不均一な評価コストの設定に古典的な期待改善を一般化する非筋力的獲得関数を提案する。
我々の獲得関数は、様々な合成問題や実問題において、既存の手法よりも優れています。
論文 参考訳(メタデータ) (2021-11-12T02:18:26Z) - Low-Cost Algorithmic Recourse for Users With Uncertain Cost Functions [74.00030431081751]
本稿では,ユーザ固有のコスト関数の概念を定式化し,ユーザのための行動可能なリコースを識別する新しい手法を提案する。
本手法は,強いベースライン法に比べて最大25.89パーセントのユーザを満足させる。
論文 参考訳(メタデータ) (2021-11-01T19:49:35Z) - Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
空間的制約が存在する場合の高次元統計量と非破壊的最適化の関連について検討する。
これらの問題に対する新規で簡単な最適化法を開発した。
結論として、効率よくステーションに収束する一階法は、これらのタスクに対して効率的なアルゴリズムを導出する。
論文 参考訳(メタデータ) (2021-09-23T17:38:24Z) - Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。
我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。
また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
論文 参考訳(メタデータ) (2021-07-02T16:21:52Z) - Regularized Online Allocation Problems: Fairness and Beyond [7.433931244705934]
本稿では, 総資源消費に作用する非線形正規化器を含む変種である, 語彙化オンライン割当問題を紹介する。
この問題では、要求は時間とともに繰り返し届き、各要求に対して、意思決定者は報酬を生成しリソースを消費するアクションを取る必要があります。
目的は、資源制約を受ける加算可分な報酬と非分離可正則化器の値とを同時に最大化することである。
論文 参考訳(メタデータ) (2020-07-01T14:24:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。