Poly-time algorithm for L-convex fn minimization
Let be an -convex function, and denote Is there a (simple) primal algorithm to find a minimizer of by using the following oracle at most poly n log T time?
Input of oracle:
Output of oracle: the value
This problem is motivated by mutil-item auction. In a multi-item auction with gross-substitutes valuation functions, the problem of finding equilibrium prices can be reduced to the minimization of a certain -convex function (called Lyapunov function), and the oracle mentioned above can be implemented if each valuation function is given with a demand oracle.
Note that the polynomial-time solvability of the problem mentioned above is already known; for example, we can apply the cutting-plane algorithm of Lee, Sidford, and Wong. We need a polynomial-time algorithm which is much simpler, due to the request from auction theory.