| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
ProductMixAuction.FujishigeWolfe
- type BitMask = Vector Bool
- type SubmodularFunction = BitMask -> Integer
- findMin :: Int -> SubmodularFunction -> BitMask
- fromBitMask :: Num a => BitMask -> Vector a
- edmondsGreedy :: SubmodularFunction -> Point -> Point
- mkPoint :: [Double] -> Point
- submodularityCheck :: Int -> SubmodularFunction -> Bool
Documentation
type SubmodularFunction = BitMask -> Integer Source #
findMin :: Int -> SubmodularFunction -> BitMask Source #
This is intended to be the main entry point.
It takes the dimension of the problem (i.e., the number of good we are considering) and the submodular function itself.
It returns the minimum norm point we find.
TODO: the submodular function currently has to evaluate to 0 on the empty set. This is easy to fix by adapting the function, and currently has to be done externally.
fromBitMask :: Num a => BitMask -> Vector a Source #
edmondsGreedy :: SubmodularFunction -> Point -> Point Source #
This algorithm is supposed to be used as the linear optimisation oracle in the main algorithm.
It is for example described in the thesis by Garcia, as Algorithm 2.
The algorithm can also be used to obtain an initial point for the main algorithm.
submodularityCheck :: Int -> SubmodularFunction -> Bool Source #