Fugu-MT 論文翻訳(概要): Edge Minimizing the Student Conflict Graph

論文の概要: Edge Minimizing the Student Conflict Graph

arxiv url: http://arxiv.org/abs/2102.06743v1
Date: Fri, 12 Feb 2021 19:54:44 GMT
ステータス: 処理完了
システム内更新日: 2021-02-16 22:21:26.747880
Title: Edge Minimizing the Student Conflict Graph
Title（参考訳）: 学生紛争グラフを最小化するエッジ
Authors: Joshua S. Friedman
Abstract要約: 学生衝突グラフ(SCG)のエッジ数を最小限に抑えるハイブリッド近似分割アルゴリズムを提供します。この分割アルゴリズムを,高度に制約された時間分割モデルに適用する。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: In many schools, courses are given in sections. Prior to timetabling students need to be assigned to individual sections. We give a hybrid approximation sectioning algorithm that minimizes the number of edges (potential conflicts) in the student conflict graph (SCG). We start with a greedy algorithm to obtain a starting solution and then continue with a constraint programming based algorithm (CP-SAT) that reduces the number of edges. We apply the sectioning algorithm to a highly constrained timetabling model which we specify.
Abstract（参考訳）: 多くの学校ではコースが設けられている。時間指定の前に、各セクションに学生を割り当てる必要があります。本稿では,学生競合グラフ(scg)におけるエッジ数(ポテンシャル競合)を最小化するハイブリッド近似分割アルゴリズムを提案する。初期解を得るための欲望のあるアルゴリズムから始めて,エッジ数を減らす制約プログラミングベースアルゴリズム(cp-sat)を継続する。この分割アルゴリズムを,高度に制約された時間分割モデルに適用する。

関連論文リスト

Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better [18.121514220195607]
クラスタ削除は、計算およびソーシャルネットワーク分析におけるNPハードグラフクラスタリングの目的である。まず,2つの近似アルゴリズムの厳密な解析を行い,その近似保証を4から3に改善する。補助グラフにおいて最大等級を優しく取り、その周囲にクラスタを形成することにより、両アルゴリズムを驚くほど単純な方法でデランドマイズすることができることを示す。
論文参考訳（メタデータ） (2024-04-24T18:39:18Z)
Graph Cuts with Arbitrary Size Constraints Through Optimal Transport [18.338458637795263]
任意のサイズ制約下でグラフを分割するグラフカットアルゴリズムを提案する。我々は,大域収束を臨界点に保証する高速化された近位GDアルゴリズムを用いてこの問題を解決する。
論文参考訳（メタデータ） (2024-02-07T10:33:09Z)
More on greedy construction heuristics for the MAX-CUT problem [8.148355685823521]
この図は, 最大カット問題に対して, 主なグリーディを分類するのに有効であることを示す。 SG(Sahni-Gonzalez)アルゴリズムの全てのバージョンはプリム類に分類される。様々なエッジ・コントラクション(EC)アルゴリズムはKruskalクラスに属する。
論文参考訳（メタデータ） (2023-12-18T02:52:04Z)
Learning the Positions in CountSketch [49.57951567374372]
本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
論文参考訳（メタデータ） (2023-06-11T07:28:35Z)
Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文参考訳（メタデータ） (2023-01-31T19:14:30Z)
Causal Bandits without Graph Learning [28.021500949026766]
我々は,原子間干渉を用いた報酬ノードの親ノード探索のための効率的なアルゴリズムを開発した。報奨ノードが複数の親を持つ場合にアルゴリズムを拡張します。
論文参考訳（メタデータ） (2023-01-26T20:27:14Z)
The Neural-Prediction based Acceleration Algorithm of Column Generation for Graph-Based Set Covering Problems [20.1479227701035]
グラフに基づく集合被覆問題の解法として,ニューラル予測(CG-P)を用いたカラム生成アルゴリズムを提案する。グラフニューラルネットワークに基づくニューラル予測モデルを用いて,各エッジの最終解に含まれる確率を予測する。鉄道員のスケジューリング問題に対するCG-Pアルゴリズムの評価を行い,ベースライン列生成アルゴリズムよりも優れていた。
論文参考訳（メタデータ） (2022-07-04T13:46:59Z)
Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond [98.92725321081994]
最先端の解法は、根底にある木探索アルゴリズムを高速化するために、無数の切削平面技術を統合している。本研究は,インスタンス分布に合わせて高い性能のカット選択ポリシーを学習するための最初の保証を証明した。
論文参考訳（メタデータ） (2021-06-08T00:57:59Z)
An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文参考訳（メタデータ） (2020-10-23T09:12:47Z)
Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
論文参考訳（メタデータ） (2020-08-29T14:58:26Z)
Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文参考訳（メタデータ） (2020-06-24T11:37:33Z)

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