現在、近似アルゴリズムを学んでいます。LP で Vertex Cover を学んだとき、Bounding Principles という原則に出会いました。それはこのように：
(1) ILP 問題の最大値は、常に LP 緩和の最大値以下です。
ILP の MAX ≤ LP 緩和の MAX
(2) ILP 問題の最小値は、常に LP 緩和の最小値以上です。
ILP の MIN ≥ LP 緩和の MIN
「ILP の MAX ≤ LP 緩和の MAX」と「ILP の MIN ≥ LP 緩和の MIN」の理由がわかりません。
誰でも説明できますか、thx!