A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint

No abstract is available for this paper.

• Publication year

  2012

• Venue

  IEEE Annual Symposium on Foundations of Computer Science

• Publication date

  2012-04-20

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/FOCS.2012.55
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Oblivious and Non-oblivious Local Search for Combinatorial Optimization

  2012cited by this paper
• A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization

  2012cited by this paper
• The Power of Local Search: Maximum Coverage over a Matroid

  2012influential reference
• A (k+3)/2-approximation algorithm for monotone submodular k-set packing and general k-exchange systems

  2011cited by this paper
• Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm - (Extended Abstract)

  2011influential reference
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint

  2011cited by this paper
• Maximizing Non-Monotone Submodular Functions

  2011influential reference
• A Unified Continuous Greedy Algorithm for Submodular Maximization

  2011influential reference
• Improved Approximations for k-Exchange Systems - (Extended Abstract)

  2011cited by this paper
• Submodularity and Curvature: The Optimal Algorithm

  2010cited by this paper
• Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures

  2010cited by this paper
• Submodular maximization by simulated annealing

  2010influential reference
• Submodular Maximization over Multiple Matroids via Generalized Exchange Properties

  2009influential reference
• Non-monotone submodular maximization under matroid and knapsack constraints

  2009cited by this paper
• Optimal approximation for the submodular welfare problem in the value oracle model

  2008cited by this paper
• Submodularity and curvature : the optimal algorithm

  2008cited by this paper
• Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)

  2007cited by this paper
• Revisiting the Greedy Approach to Submodular Set Function Maximization

  2007influential reference
• Pipage Rounding: A New Method of Constructing Algorithms with Proven Performance Guarantee

  2004cited by this paper
• A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time

  2000cited by this paper
• The Budgeted Maximum Coverage Problem

  1999cited by this paper
• A threshold of ln n for approximating set cover (preliminary version)

  1996cited by this paper
• New Local Search Approximation Techniques for Maximum Generalized Satisfiability Problems

  1994cited by this paper
• On syntactic versus computational views of approximability

  1994cited by this paper
• Geometric Algorithms and Combinatorial Optimization

  1988cited by this paper
• Best Algorithms for Approximating the Maximum of a Submodular Set Function

  1978influential reference
• An analysis of approximations for maximizing submodular set functions—I

  1978cited by this paper
• Convergence Properties of Padé Approximants to exp (z) and Their Derivatives

  1973cited by this paper
• Matroids and the greedy algorithm

  1971cited by this paper
• Comments on bases in dependence structures

  1969cited by this paper
• Note on Independence Functions

  1957cited by this paper
• Sur la représentation approchée d'une fonction par des fractions rationnelles

  year unknowncited by this paper

• Communication-Efficient Data Exchange for Decentralized Loop-Closure Detection in Collaborative SLAM

  2025cites this paper
• Optimizing Monitoring Utility of Uncrewed Aerial Vehicles Considering Adverse Effects

  2025cites this paper
• Subquadratic Submodular Maximization with a General Matroid Constraint

  2024cites this paper
• From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization

  2024cites this paper
• An Approximation Algorithm for the h-Hop Independently Submodular Maximization Problem and Its Applications

  2023cites this paper
• Greedy Selection for Heterogeneous Sensors

  2023influential citation
• Matroid-Constrained Vertex Cover

  2023cites this paper
• Supermodular Rank: Set Function Decomposition and Optimization

  2023influential citation
• Coresets remembered and items forgotten: submodular maximization with deletions

  2022cites this paper
• Optimal deletion-robust coreset for submodular maximization

  2022cites this paper
• Ordered Submodularity and its Applications to Diversifying Recommendations

  2022cites this paper
• Efficient Optimization of Partition Scan Statistics via the Consecutive Partitions Property

  2022cites this paper
• Maximizing h-hop Independently Submodular Functions Under Connectivity Constraint

  2022cites this paper
• Matroid-Constrained Maximum Vertex Cover: Approximate Kernels and Streaming Algorithms

  2022cites this paper
• The Network Visibility Problem

  2021cites this paper
• Improved Streaming Algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraint

  2021cites this paper
• A Tight Deterministic Algorithm for the Submodular Multiple Knapsack Problem

  2021cites this paper
• Submodular Order Functions and Assortment Optimization

  2021cites this paper
• Efficient and Effective Algorithms for Revenue Maximization in Social Advertising

  2021cites this paper
• Submodular + Concave

  2021cites this paper
• Two-Sided Weak Submodularity for Matroid Constrained Optimization and Regression

  2021influential citation
• Sensor Planning for Large Numbers of Robots

  2021cites this paper
• On the Approximation Relationship between Optimizing Ratio of Submodular (RS) and Difference of Submodular (DS) Functions

  2021cites this paper
• Approximation Algorithms for the Generalized Team Orienteering Problem and its Applications

  2021cites this paper
• A General Framework for Fairness in Multistakeholder Recommendations

  2020cites this paper
• Simple Deterministic Approximation for Submodular Multiple Knapsack Problem

  2020cites this paper
• Approximation Algorithms for the Team Orienteering Problem

  2020cites this paper
• Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model

  2020cites this paper
• Deterministic Algorithms for the Submodular Multiple Knapsack Problem

  2020cites this paper
• A note on solving DiDi’s driver-order matching problem

  2020cites this paper
• Tight Algorithms for the Submodular Multiple Knapsack Problem

  2020cites this paper
• Exploiting Structure of Uncertainty for Efficient Combinatorial Semi-Bandits

  2019influential citation
• Maximize a Monotone Function with a Generic Submodularity Ratio

  2019cites this paper
• Sequence submodular maximization meets streaming

  2019cites this paper
• Diverse data selection via combinatorial quasi-concavity of distance covariance: A polynomial time global minimax algorithm

  2019cites this paper
• Exploiting structure of uncertainty for efficient matroid semi-bandits

  2019cites this paper
• Optimal Cache Allocation for Named Data Caching under Network-Wide Capacity Constraint

  2018cites this paper
• Non-submodular Function Maximization subject to a Matroid Constraint, with Applications

  2018cites this paper
• Randomized Strategies for Robust Combinatorial Optimization

  2018cites this paper
• Self-Improving Crowdsourcing: Near-Effortless Design of Adaptive Distributed Work

  2018cites this paper
• Online Submodular Maximization with Free Disposal

  2018cites this paper
• On the Network Visibility Problem

  2018cites this paper
• Distributed matroid-constrained submodular maximization for multi-robot exploration: theory and practice

  2018cites this paper
• Distributed Submodular Maximization on Partition Matroids for Planning on Large Sensor Networks

  2018cites this paper
• When Online Dating Meets Nash Social Welfare: Achieving Efficiency and Fairness

  2018cites this paper
• Multi-Pass Streaming Algorithms for Monotone Submodular Function Maximization

  2018cites this paper
• Nearly Linear Time Algorithms and Lower Bound for Submodular Maximization

  2018cites this paper
• The Role of Information in Distributed Resource Allocation

  2017cites this paper
• Robust Guarantees of Stochastic Greedy Algorithms

  2017cites this paper
• New algorithms for distributed submodular maximization

  2017cites this paper
• Efficient Online Multi-robot Exploration via Distributed Sequential Greedy Assignment

  2017cites this paper
• Constrained Submodular Maximization via Greedy Local Search

  2017cites this paper
• Interleaved Algorithms for Constrained Submodular Function Maximization

  2017cites this paper
• Crowdsourcing with Diverse Groups of Users

  2017cites this paper
• Streaming Algorithms for Maximizing Monotone Submodular Functions Under a Knapsack Constraint

  2017cites this paper
• An Algorithmic Game Approach for Demand Side Management in Smart Grid with Distributed Renewable Power Generation and Storage

  2016cites this paper
• Online Submodular Maximization with Free Disposal: Randomization Beats ¼ for Partition Matroids

  2016cites this paper
• On maximizing a monotone k-submodular function subject to a matroid constraint

  2016cites this paper
• Informative path planning as a maximum traveling salesman problem with submodular rewards

  2015cites this paper
• Notes on Greedy Algorithms for Submodular Maximization Thibaut

  2015cites this paper
• Understanding and Improving Online Social Interactions and Processes: Methods, Algorithms and Applications

  2015cites this paper
• Learning-Based Compressive Subsampling

  2015cites this paper
• Gaze-enabled egocentric video summarization via constrained submodular maximization

  2015cites this paper
• Refining Social Graph Connectivity via Shortcut Edge Addition

  2015cites this paper
• Parallel Task Routing for Crowdsourcing

  2014cites this paper
• Approximation for maximizing monotone non-decreasing set functions with a greedy method

  2014cites this paper
• Fast algorithms for maximizing submodular functions

  2014influential citation
• Submodular Maximization with Cardinality Constraints

  2014cites this paper
• Informative Path Planning and Sensor Scheduling for Persistent Monitoring Tasks

  2013cites this paper
• An accelerated continuous greedy algorithm for maximizing strong submodular functions

  2013cites this paper
• Near optimality of greedy strategies for string submodular functions with forward and backward curvature constraints

  2013cites this paper
• String Submodular Functions With Curvature Constraints

  2013cites this paper
• Monotone Submodular Maximization over a Matroid

  2013cites this paper
• Inequalities on submodular functions via term rewriting

  2013cites this paper
• Knapsack Cover Subject to a Matroid Constraint

  2013cites this paper
• Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization

  2013cites this paper
• Optimal approximation for submodular and supermodular optimization with bounded curvature

  2013influential citation
• Density Functions subject to a Co-Matroid Constraint

  2012cites this paper
• Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search

  2012cites this paper
• Oblivious and Non-oblivious Local Search for Combinatorial Optimization

  2012cites this paper
• Submodular Functions: Learnability, Structure, and Optimization

  2010cites this paper