submodular functions

Trioid: A generalization of matroid and the associated polytope

  • Santosh N. Kabadi
  • Abraham Punnen
    • Categories Combinatorial Optimization, Graphs and Matroids, Polyhedra Tags , ,

    We consider a generalization of the well known greedy algorithm, called $m$-step greedy algorithm, where $m$ elements are examined in each iteration. When $m=1$ or $2$, the algorithm reduces to the standard greedy algorithm. For $m=3$ we provide a complete characterization of the independence system, called trioid, where the $m$-step greedy algorithm guarantees an optimal … Read more

    Polymatroids and Mean-Risk Minimization in Discrete Optimization

  • Alper Atamturk
  • Vishnu Narayanan
    • Categories (Mixed) Integer Nonlinear Programming, Graphs and Matroids, Integer Programming Tags , , ,

    In financial markets high levels of risk are associated with large returns as well as large losses, whereas with lower levels of risk, the potential for either return or loss is small. Therefore, risk management is fundamentally concerned with finding an optimal trade-off between risk and return matching an investor’s risk tolerance. Managing risk is … Read more