二変数の凸区分線形格子最適化
二つの整数parameter上の凸区分線形目的について、折れ目直線の交点から連続最小候補を作り、定数半径内に整数最適解があることを証明して有限格子点へ縮約する。
この典型を扱う単元: 二変数の凸区分線形整数最適化
検索別名: two-variable convex lattice optimization、二変数凸格子最適化、二変数区分線形凸最適化
未知問からこの典型を見つける手掛かり
- 扱う対象
- 二つの整数parameter
- 凸区分線形目的関数
- 格子点
- 使う手掛かり
- 二変数の整数最適化
- 有限本の折れ目直線
- 連続最小点近傍の格子候補
- 保つ不変量
- 凸性
- 折れ目直線の交点
- 整数最適点までの定数距離
- 求めるもの
- 大域最適解
- 整数最小値
- 有限近傍の全探索
- 適用しない条件
- 一変数の傾き単調性だけで最小点を探す目的関数
分類・前提・学習成果
分類と直接の前提
概念上の親: 幾何・凸最適化への変換
関連する典型
学習成果と学習単位
二変数の凸区分線形目的について折れ目直線の交点で連続最小候補を求め、定数距離内に整数最適点があることを証明して有限個の近傍格子点だけを評価できる。
二変数の凸区分線形整数最適化で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC459 G「Golf 2」 公式問題主題: 二変数の凸区分線形整数最適化 / 主タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC459 G「Golf 2」 公式問題主題: 二変数の凸区分線形整数最適化 / 主タグ