Abstract
Can a function f defined on some domain \(\mathcal {D}\) be extended to a submodular function on a larger domain \(\mathcal {D}' \supset \mathcal {D}\)? This is the problem of submodular partial function extension. In this work, we develop a new combinatorial certificate of nonextendibility called a square certificate. We then present two applications of our certificate: to submodular extension on lattices, and to property testing of submodularity.
- For lattices, we define a new class of lattices called pseudocyclic lattices that strictly generalize modular lattices, and show that these are sublattice extendible, i.e., a partial function that is submodular on a sublattice is extendible to a submodular function on the lattice. We give an example to show that in general lattices this property does not hold.
- For property testing, we show general lower bounds for a class of submodularity testers called proximity oblivious testers. One of our lower bounds is applicable to matroid rank functions as well, and is the first lower bound for this class of functions.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
To be precise, this is true of one-sided testers, which must accept if a function satisfies the property.
- 2.
A function \(f:2^{[m]} \rightarrow \mathbb {Z}_{\ge 0}\) is a matroid rank function if (i)\(f(\emptyset ) = 0\), (ii)\(f(S \cup i) - f(S) \in \{0,1\}\) for any S and \(i \not \in S\) and (iii)f is submodular.
- 3.
There exist constant query POTs with \(\rho (\epsilon ) = \epsilon /O(m),\epsilon /O(m),\epsilon /O(m^{1.5})\) respectively. These imply \(O(m),O(m),O(m^{1.5})\)-query POTs with \(\rho (\epsilon ) = \epsilon \).
- 4.
E.g., in Fig. 1a, the multisets \(\{(a,e,b,d),(d,h,e,g)\}\) and \(\{(a,h,b,g)\}\) are similar (with \(k = 1\)).
- 5.
This is because we are dealing with one-sided testers. If a function has the property then the tester must accept the function.
References
Blum, M., Luby, M., Rubinfeld, R.: Self-testing/correcting with applications to numerical problems. J. Comput. Syst. Sci. 47(3), 549–595 (1993)
Chakrabarty, D., Seshadhri, C.: Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids. In: STOC, pp. 419–428. ACM (2013)
Goldreich, O., Goldwasser, S., Lehman, E., Ron, D., Samorodnitsky, A.: Testing monotonicity. Combinatorica 20(3), 301–337 (2000). https://doi.org/10.1007/s004930070011
Goldreich, O., Ron, D.: On proximity-oblivious testing. SIAM J. Comput. 40(2), 534–566 (2011)
Grätzer, G.: Lattice Theory: Foundation. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-0348-0018-1
Kempe, D., Kleinberg, J.M., Tardos, É.: Maximizing the spread of influence through a social network. Theory of Computing 11, 105–147 (2015)
Kolmogorov, V., Zabih, R.: What energy functions can be minimized via graph cuts? IEEE Trans. Pattern Anal. Mach. Intell. 26(2), 147–159 (2004)
Krokhin, A., Larose, B.: Maximizing supermodular functions on product lattices, with application to maximum constraint satisfaction. SIAM J. Discret. Math. 22(1), 312–328 (2008)
Kuivinen, F.: On the complexity of submodular function minimisation on diamonds. Discret. Optim. 8(3), 459–477 (2011)
Lehmann, B., Lehmann, D.J., Nisan, N.: Combinatorial auctions with decreasing marginal utilities. Games Econ. Behav. 55(2), 270–296 (2006)
Pitt, L., Valiant, L.G.: Computational limitations on learning from examples. J. ACM 35(4), 965–984 (1988)
Promislow, S.D., Young, V.R.: Supermodular functions on finite lattices. Order 22(4), 389–413 (2005). https://doi.org/10.1007/s11083-005-9026-5
Seshadhri, C., Vondrák, J.: Is submodularity testable? Algorithmica 69(1), 1–25 (2014). https://doi.org/10.1007/s00453-012-9719-2
Topkis, D.M.: Minimizing a submodular function on a lattice. Oper. Res. 26(2), 305–321 (1978)
Topkis, D.M.: Equilibrium points in nonzero-sum n-person submodular games. SIAM J. Control Optim. 17(6), 773–787 (1979)
Varian, H.: Revealed preference. Samuelsonian economics and the twenty-first century, pp. 99–115 (2006)
Acknowledgements
Both authors acknowledge support from the Department of Atomic Energy, Government of India (project no. RTI4001). The first author is additionally supported by a Ramanujan Fellowship (SERB - SB/S2/RJN-055/2015) and an Early Career Research Award (SERB - ECR/2018/002766). The second author is additionally supported by a research fellowship from Tata Consultancy Services.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Bhaskar, U., Kumar, G. (2020). A Non-Extendibility Certificate for Submodularity and Applications. In: Kim, D., Uma, R., Cai, Z., Lee, D. (eds) Computing and Combinatorics. COCOON 2020. Lecture Notes in Computer Science(), vol 12273. Springer, Cham. https://doi.org/10.1007/978-3-030-58150-3_49
Download citation
DOI: https://doi.org/10.1007/978-3-030-58150-3_49
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-58149-7
Online ISBN: 978-3-030-58150-3
eBook Packages: Computer ScienceComputer Science (R0)