discrete convexity

Greedy Systems of Linear Inequalities and Lexicographically Optimal Solutions

  • Satoru Fujishige
    • Categories Combinatorial Optimization Tags , ,

    The present note reveals the role of the concept of greedy system of linear inequalities played in connection with lexicographically optimal solutions on convex polyhedra and discrete convexity. The lexicographically optimal solutions on convex polyhedra represented by a greedy system of linear inequalities can be obtained by a greedy procedure, a special form of which … Read more

    Approximating Convex Functions By Non-Convex Oracles Under The Relative Noise Model

  • Nir Halman
    • Categories Approximation Algorithms Tags ,

    We study succinct approximation of functions that have noisy oracle access. Namely, construction of a succinct representation of a function, given oracle access to an L-approximation of the function, rather than to the function itself. Specifically, we consider the question of the succinct representation of an approximation of a convex function v that cannot be … Read more