論文の概要: Approximating Optimal Labelings for Temporal Connectivity
- arxiv url: http://arxiv.org/abs/2504.16837v1
- Date: Wed, 23 Apr 2025 16:00:33 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-02 15:25:55.231456
- Title: Approximating Optimal Labelings for Temporal Connectivity
- Title（参考訳）: 時間接続性のための最適ラベルの近似
- Authors: Daniele Carnevale, Gianlorenzo D'Angelo, Martin Olsen,
- Abstract要約: 時間グラフのエッジの可利用時間を、与えられた最大許容時間$a$で全ての頂点が接続されるようにスケジューリングする問題について検討する。
この問題は、EmphMinimum Aged Labeling (MAL)として知られるもので、ロジスティクス、流通スケジューリング、ソーシャルネットワークに広がる情報にいくつかの応用がある。
- 参考スコア（独自算出の注目度）: 7.394099294390271
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In a temporal graph the edge set dynamically changes over time according to a set of time-labels associated with each edge that indicates at which time-steps the edge is available. Two vertices are connected if there is a path connecting them in which the edges are traversed in increasing order of their labels. We study the problem of scheduling the availability time of the edges of a temporal graph in such a way that all pairs of vertices are connected within a given maximum allowed time $a$ and the overall number of labels is minimized. The problem, known as \emph{Minimum Aged Labeling} (MAL), has several applications in logistics, distribution scheduling, and information spreading in social networks, where carefully choosing the time-labels can significantly reduce infrastructure costs, fuel consumption, or greenhouse gases. The problem MAL has previously been proved to be NP-complete on undirected graphs and \APX-hard on directed graphs. In this paper, we extend our knowledge on the complexity and approximability of MAL in several directions. We first show that the problem cannot be approximated within a factor better than $O(\log n)$ when $a\geq 2$, unless $\text{P} = \text{NP}$, and a factor better than $2^{\log ^{1-\epsilon} n}$ when $a\geq 3$, unless $\text{NP}\subseteq \text{DTIME}(2^{\text{polylog}(n)})$, where $n$ is the number of vertices in the graph. Then we give a set of approximation algorithms that, under some conditions, almost match these lower bounds. In particular, we show that the approximation depends on a relation between $a$ and the diameter of the input graph. We further establish a connection with a foundational optimization problem on static graphs called \emph{Diameter Constrained Spanning Subgraph} (DCSS) and show that our hardness results also apply to DCSS.
- Abstract（参考訳）: 時間グラフでは、エッジが利用可能な時間ステップを示す各エッジに関連付けられた時間ラベルのセットに従って、エッジセットが時間とともに動的に変化する。
2つの頂点が接続されている場合、エッジがラベルの順に進行する経路が存在する。
時間グラフのエッジの可利用時間を、与えられた最大許容時間$a$で全ての頂点が接続され、ラベルの総数が最小となるようにスケジューリングする問題について検討する。
この問題は 'emph{Minimum Aged Labeling} (MAL) と呼ばれ、ロジスティクス、流通スケジューリング、ソーシャルネットワークにおける情報拡散においていくつかの応用があり、タイムラベルを慎重に選択することでインフラコスト、燃料消費、温室効果ガスを著しく削減することができる。
MALの問題は、以前は無向グラフ上でNP完全であることが証明され、有向グラフ上では \APX-hard である。
本稿では,MALの複雑さと近似性に関する知識を,いくつかの方向に拡張する。
O(\log n)$ が$a\geq 2$ なら$a\geq 2$ で、$\text{P} = \text{NP}$ が$2^{\log ^{1-\epsilon} n}$ で$a\geq 3$ が$\text{NP}\subseteq \text{DTIME}(2^{\text{polylog}(n)} でなければ$n$ はグラフの頂点の数である。
そして、ある条件下では、これらの下界にほぼ一致する近似アルゴリズムのセットを与える。
特に、近似は入力グラフの直径と$a$の関係に依存することを示す。
さらに,DCSS (emph{Diameter Constrained Spanning Subgraph}) と呼ばれる静的グラフの基本最適化問題との接続を確立し,その硬さがDCSSにも適用可能であることを示す。
関連論文リスト
- Linear Causal Bandits: Unknown Graph and Soft Interventions [18.412177974475526]
因果バンディットのアルゴリズムを 設計するのは 2つの前提に依る
その一般的な形式、すなわち未知グラフと未知の介入モデルにおける問題は、まだ未解決のままである。
本稿は、この問題に対処し、N$ノードを持つグラフにおいて、最大$d$と最大$L$の因果経路長を持つグラフにおいて、$T$相互作用が後悔の上限スケールをラウンド化することを示す。
論文 参考訳（メタデータ） (2024-11-04T18:50:39Z) - Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。
我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。
提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
論文 参考訳（メタデータ） (2024-08-03T20:08:02Z) - Exact Algorithms and Lowerbounds for Multiagent Pathfinding: Power of
Treelike Topology [0.0]
我々は、与えられたグラフの$G上の一組の$kエージェントの経路を効率的に見つけることに重点を置いており、各エージェントはそのソースからターゲットへの経路を求める。
解の質の重要な尺度は提案されたスケジュールの長さ$ell$、すなわち最長経路の長さである。
MAPFは$G$+$ell$に対してW[1]ハードであり、FPTは$G$+$ell$であることを示す。
論文 参考訳（メタデータ） (2023-12-15T09:42:46Z) - Dynamic algorithms for k-center on graphs [3.568439282784197]
エッジ更新を行う動的グラフ上での$k$-center問題に対する最初の効率的なアルゴリズムを提供する。
完全に動的な$(2+epsilon)$-approximationアルゴリズムを$k$-center問題に対して提案する。
論文 参考訳（メタデータ） (2023-07-28T13:50:57Z) - Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。
我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。
技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
論文 参考訳（メタデータ） (2022-10-15T09:22:22Z) - Horizon-Free Reinforcement Learning in Polynomial Time: the Power of
Stationary Policies [88.75843804630772]
我々は既存の境界に対して,$Oleft(mathrmpoly(S,A,log K)sqrtKright)を後悔するアルゴリズムを設計する。
この結果は、定常政策の近似力、安定性、および濃度特性を確立する新しい構造補題の列に依存している。
論文 参考訳（メタデータ） (2022-03-24T08:14:12Z) - A sublinear query quantum algorithm for s-t minimum cut on dense simple
graphs [1.0435741631709405]
グラフにおける$soperatorname-t$最小カットは、削除が$s$と$t$を切断するエッジの最小ウェイトサブセットに対応する。
この研究では、無向グラフ上の最小$soperatorname-t$カット問題に対する量子アルゴリズムを記述する。
論文 参考訳（メタデータ） (2021-10-29T07:35:46Z) - Random Subgraph Detection Using Queries [29.192695995340653]
植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。
本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。
このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
論文 参考訳（メタデータ） (2021-10-02T07:41:17Z) - Projection-free Graph-based Classifier Learning using Gershgorin Disc
Perfect Alignment [59.87663954467815]
グラフベースのバイナリ学習では、既知のラベルのサブセット$hatx_i$を使って未知のラベルを推論する。
ラベルの$x_i$をバイナリ値に制限する場合、問題はNPハードである。
代わりに線形プログラム(LP)の列を解くことにより,高速なプロジェクションフリー手法を提案する。
論文 参考訳（メタデータ） (2021-06-03T07:22:48Z) - Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
実用的な単一ループ加速勾配追跡には$O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$が必要であることを証明している。
我々の収束率は$O(frac1epsilon5/7)$と$O(fracLmu)5/7frac1(1-sigma)1.5logfrac1epsilon)$よりも大幅に改善した。
論文 参考訳（メタデータ） (2021-04-06T15:34:14Z) - Random Graph Matching with Improved Noise Robustness [2.294014185517203]
本稿では確率モデルに基づくグラフマッチングの新しいアルゴリズムを提案する。
我々のアルゴリズムは、$alpha le 1 / (log log n)C$ のとき、その基礎となるマッチングを高い確率で復元する。
これにより、以前の作業で達成された条件 $alpha le 1 / (log n)C$ が改善される。
論文 参考訳（メタデータ） (2021-01-28T02:39:27Z) - Learning Bayesian Networks Under Sparsity Constraints: A Parameterized
Complexity Analysis [7.99536002595393]
本稿では,ネットワーク上あるいはそのモラル化されたグラフ上に制約を加える際に,最適なベイズネットワークの構造を学習する問題について検討する。
モラル化されたグラフに少なくとも$k$のエッジを持つ最適ネットワークを学習すると、おそらく$f(k)cdot |I|O(1)$-timeアルゴリズムが存在しない。
論文 参考訳（メタデータ） (2020-04-30T12:31:13Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳（メタデータ） (2020-02-17T18:41:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。