The Complexity of Partial Function Extension for Coverage Functions

DOI10.4230/LIPICS.APPROX-RANDOM.2019.30OpenAlexW2977488512MaRDI QIDQ5875484FDOQ5875484

Authors: Umang Bhaskar, Gunjan Kumar 

Publication date: 3 February 2023

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

zbMATH Keywords

approximation algorithmPAC learningcoverage functionspartial function extension

Mathematics Subject Classification ID

Randomized algorithms (68W20) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites Work

• Title not available (Why is that?)
• Convex functions on non-convex domains
• Geometric algorithms and combinatorial optimization.
• Minimizing a Submodular Function on a Lattice
• Is submodularity testable?
• Combinatorial auctions with decreasing marginal utilities
• Computational limitations on learning from examples
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• Roofs and convexity
• The complexity status of problems related to sparsest cuts
• Learning submodular functions
• Extension of convex function
• Error-free and best-fit extensions of partially defined Boolean functions
• Maximizing social influence in nearly optimal time
• Title not available (Why is that?)
• Sketching valuation functions
• The smallest convex extensions of a convex function
• A non-extendibility certificate for submodularity and applications
• The limitations of optimization from samples
• General truthfulness characterizations via convex analysis
• Recognizing Coverage Functions

Cited In (2)

• Title not available (Why is that?)
• Positivity and convexity in incomplete cooperative games

This page was built for publication: The Complexity of Partial Function Extension for Coverage Functions

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