論文の概要: Asymptotically Smaller Encodings for Graph Problems and Scheduling

• arxiv url: http://arxiv.org/abs/2506.14042v1
• Date: Mon, 16 Jun 2025 22:31:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-18 17:34:59.262193
• Title: Asymptotically Smaller Encodings for Graph Problems and Scheduling
• Title（参考訳）: グラフ問題とスケジューリングのための漸近的に小さな符号化
• Authors: Bernardo Subercaseaux,
• Abstract要約: いくつかのグラフ問題を、多くの節に対して$O(|V|2 / lg |V|)$のみを用いてCNFにエンコードできることを示す。 O(|V| lg |V|)$節のみを用いるような高密度区間グラフにおける独立集合に対する新しい符号化も示す。
• 参考スコア（独自算出の注目度）: 4.73194777046253
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We show how several graph problems (e.g., vertex-cover, independent-set, $k$-coloring) can be encoded into CNF using only $O(|V|^2 / \lg |V|)$ many clauses, as opposed to the $\Omega(|V|^2)$ constraints used by standard encodings. This somewhat surprising result is a simple consequence of a result of Erd\H{o}s, Chung, and Spencer (1983) about biclique coverings of graphs, and opens theoretical avenues to understand the success of "Bounded Variable Addition'' (Manthey, Heule, and Biere, 2012) as a preprocessing tool. Finally, we show a novel encoding for independent sets in some dense interval graphs using only $O(|V| \lg |V|)$ clauses (the direct encoding uses $\Omega(|V|^2)$), which we have successfully applied to a string-compression encoding posed by Bannai et al. (2022). As a direct byproduct, we obtain a reduction in the encoding size of a scheduling problem posed by Mayank and Modal (2020) from $O(NMT^2)$ to $O(NMT + M T^2 \lg T)$, where $N$ is the number of tasks, $T$ the total timespan, and $M$ the number of machines.
• Abstract（参考訳）: いくつかのグラフ問題(例えば、頂点被覆、独立集合、$k$-coloring)が標準符号化で使われる$\Omega(|V|^2)$制約とは対照的に、単に$O(|V|^2 / \lg |V|)$多くの節でCNFにエンコードできることを示す。 このやや驚くべき結果は、エルド・H{o}s, Chung, and Spencer (1983) のグラフの双斜被覆に関する単純な結果であり、「境界変数付加」(Manthey, Heule, and Biere, 2012) の成功を前処理ツールとして理解するために理論上の道を開く。 最後に、ある高密度区間グラフにおける独立集合に対して、$O(|V| \lg |V|)$節(直接符号化は$\Omega(|V|^2)$)のみを使用し、Bannai et al (2022) による文字列圧縮符号化に成功していることを示す。 直接副産物として、Mayank and Modal (2020) が提示するスケジューリング問題の符号化サイズを$O(NMT^2)$から$O(NMT + M T^2 \lg T)$に減らし、$N$はタスク数、$T$はトータルタイムパン、$M$はマシン数となる。

関連論文リスト

• Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
  携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。 我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。 提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
  論文  参考訳（メタデータ） (2024-08-03T20:08:02Z)
• Almost linear time differentially private release of synthetic graphs [6.076406622352115]
  本稿では,指数関数的メカニズムから,ほぼ線形時間と空間のアルゴリズムをサンプリングする。 直接的な結果として、差分入力を指数関数的に大きな$G$mエッジとして定義する。 これらは合成グラフを公開するためのプライベートファーストのプライベートアルゴリズムである。
  論文  参考訳（メタデータ） (2024-06-04T09:44:24Z)
• Batched Stochastic Bandit for Nondegenerate Functions [8.015503209312786]
  本稿では,非退化関数に対するバッチ帯域学習問題について検討する。 本稿では,非退化関数に対するバッチバンドイット問題をほぼ最適に解くアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-09T12:50:16Z)
• Some Notes on the Sample Complexity of Approximate Channel Simulation [2.4554686192257424]
  チャネルシミュレーションアルゴリズムは、所定のターゲット分布のランダムサンプルを$Q$で効率的にエンコードし、機械学習ベースの損失データ圧縮における応用を見つけることができる。 本稿では,固定ランタイムを用いた近似スキームについて考察する。 D_KL[Q Vert P] + o(1)) Big/epsilonbigのみのサンプル複雑さで、$mathrmTV[Q Vert P] leq epsilon$を確保し、最適な符号化性能を維持するために、グローバルバウンドの深度制限A*符号化を利用する。
  論文  参考訳（メタデータ） (2024-05-07T14:44:41Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。 すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
  論文  参考訳（メタデータ） (2022-09-04T10:01:39Z)
• Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions [51.19236668224547]
  テンソルの低階近似について検討し,テンソルトレインとタッカー分解に着目した。 テンソル列車の分解には、小さなビクリテリアランクを持つビクリテリア$(1 + eps)$-approximationアルゴリズムと、O(q cdot nnz(A))$ランニングタイムを与える。 さらに、任意のグラフを持つテンソルネットワークにアルゴリズムを拡張します。
  論文  参考訳（メタデータ） (2022-07-15T11:55:09Z)
• Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits [99.86860277006318]
  本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。 Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。 この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
  論文  参考訳（メタデータ） (2022-02-12T21:55:44Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Partially Concatenated Calderbank-Shor-Steane Codes Achieving the Quantum Gilbert-Varshamov Bound Asymptotically [36.685393265844986]
  我々は,量子-Omega-Varshamovを有界に達成する量子誤り訂正符号の新たなファミリを構築する。 $mathscrQ$は$O(N)$とdeep $O(sqrtN)$の回路で非常に効率的に符号化できる。 $mathscrQ$は$O(sqrtN)$timeで並列に復号することもできる。
  論文  参考訳（メタデータ） (2021-07-12T03:27:30Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。