scientific article; zbMATH DE number 7765404

DOI10.4230/LIPICS.ISAAC.2020.46MaRDI QIDQ6087218zbMATH OpenFDO

Authors Umang Bhaskar, Gunjan Kumar

Publication date 14 November 2023

Full work available at URL https://arxiv.org/abs/1812.05821

zbMATH Keywords

approximation algorithmslearningmatroid rankpartial function extensionproperty testingsubadditivity

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A non-extendibility certificate for submodularity and applications
• Analytical approach to parallel repetition
• Bounds on the rate of disjunctive codes
• Combinatorial auctions with decreasing marginal utilities
• Computational limitations on learning from examples
• Convex functions on non-convex domains
• Entanglement of formation of an arbitrary state of two qubits
• Error-free and best-fit extensions of partially defined Boolean functions
• Families of finite sets in which no set is covered by the union of \(r\) others
• scientific article; zbMATH DE number 5567196 (Why is no real title available?)
• Is submodularity testable?
• Learning submodular functions
• Minimizing a Submodular Function on a Lattice
• On maximizing welfare when utility functions are subadditive
• On Testing Convexity and Submodularity
• On the Abstract Properties of Linear Dependence
• Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids
• Recognizing graphic matroids
• Sketching valuation functions
• The Complexity of Partial Function Extension for Coverage Functions
• The complexity of satisfiability problems
• Two Randomized Mechanisms for Combinatorial Auctions
• Welfare guarantees for combinatorial auctions with item bidding

Cited in

(2)

• Incomplete cooperative games with player-centered information
• Positivity and convexity in incomplete cooperative games

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6087218)