Matroid rank functions and discrete concavity
Tóm tắt
We discuss the relationship between matroid rank functions and a concept of discrete concavity called
$${{\rm M}^{\natural}}$$
-concavity. It is known that a matroid rank function and its weighted version called a weighted rank function are
$${{\rm M}^{\natural}}$$
-concave functions, while the (weighted) sum of matroid rank functions is not
$${{\rm M}^{\natural}}$$
-concave in general. We present a sufficient condition for a weighted sum of matroid rank functions to be an
$${{\rm M}^{\natural}}$$
-concave function, and show that every weighted rank function can be represented as a weighted sum of matroid rank functions satisfying this condition.
Tài liệu tham khảo
Calinescu, G., Chekuri, C., Pál, M., Vondrák, J.: Maximizing a submodular set function subject to a matroid constraint. In: Integer Programming and Combinatorial Optimization, 12th International IPCO Conference. Lecture Notes in Computer Science, vol. 4513, pp. 182–196. Springer, Berlin (2007)
Dughmi, S.: A truthful randomized mechanism for combinatorial public projects via convex optimization. In: Proceedings of the 12th ACM Conference on Electronic Commerce (EC-2011), pp. 263–272. ACM, New York (2011)
Dress A.W.M., Wenzel W.: Valuated matroids. Adv. Math. 93, 214–250 (1992)
Dughmi, S., Roughgarden, T., Sundararajan, M.: Revenue submodularity. In: Proceedings of the 10th ACM Conference on Electronic Commerce (EC-2009), pp. 243–252. ACM, New York (2009)
Dughmi, S., Roughgarden, T., Yan, Q.: From convex optimization to randomized mechanisms: toward optimal combinatorial auctions. In: Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, pp. 149–158. ACM, New York (2011)
Dughmi, S., Vondrák, J.: Limitations of randomized mechanisms for combinatorial auctions. In: Proceedings of IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, pp. 502–511. IEEE, Los Alamitos (2011)
Frank A., Frank A.: Generalized polymatroids and submodular flows. Math. Progr. 42, 489–563 (1988)
Fujishige S.: Submodular Functions and Optimization. 2nd edn. Elsevier, Amsterdam (2005)
Fujishige S., Yang S.: A note on Kelso and Crawford’s gross substitutes condition. Math. Oper. Res. 28, 463–469 (2003)
Iwata S., Murota K., Shigeno M.: A fast submodular intersection algorithm for strong map sequences. Math. Oper. Res. 22, 803–813 (1997)
Lehmann B., Lehmann D.J., Nisan N.: Combinatorial auctions with decreasing marginal utilities. Games Econ. Behav. 55, 270–296 (2006)
Murota K.: Discrete convex analysis. Math. Progr. 83, 313–371 (1998)
Murota K.: Discrete Convex Analysis. SIAM, Philadelphia (2003)
Murota K.: Submodular function minimization and maximization in discrete convex analysis. RIMS Kokyuroku Bessatsu B23, 193–211 (2010)
Murota K., Shioura A.: M-convex function on generalized polymatroid. Math. Oper. Res. 24, 95–105 (1999)
Oxley J.: Matroid Theory. Oxford University Press, New York (1992)
Reijnierse H., van Gellekom A., Potters J.A.M.: Verifying gross substitutability. Econ. Theory 20, 767–776 (2002)
Schrijver A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003)
Shioura A.: On the pipage rounding algorithm for submodular function maximization: a view from discrete convex analysis. Discret. Math. Algorithms Appl. 1, 1–23 (2009)
Tardos, É.:Generalized matroids and supermodular colourings. In: Recski A.,Lovász L. (eds.) Matroid Theory, Colloquia Mathematica Societatis János Bolyai 40, pp. 359–382. North-Holland, Amsterdam (1985)
Welsh D.J.A.: Matroid Theory. Academic Press, London (1976)
Welsh D.J.A. (1995) Matroids: fundamental concepts. In: Graham R.L., Grötschel M., Lovász L. (eds.) Handbook of Combinatorics, pp. 481–526. Elsevier, Amsterdam.