Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations

https://hochbaum.ieor.berkeley.edu/html/pub/EJOR-3var.pdf

IPの制約がMonotoneのときは、minCutに帰着して多項式時間でhalfintegral解が求まるっぽい。目的関数は非線形でもいいらしい。

あとで読む。