Submodular Maximization with Cardinality Constraints

No abstract is available for this paper.

• Publication year

  2014

• Venue

  ACM-SIAM Symposium on Discrete Algorithms

• Publication date

  2014-01-05

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/1.9781611973402.106
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Combinatorial Optimization Networks And Matroids

  2016cited by this paper
• Approximating the least core value and least core of cooperative games with supermodular costs

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

  2012cited by this paper
• A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint

  2012cited by this paper
• Better Balance by Being Biased

  2012cited by this paper
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint

  2011influential reference
• Submodularity beyond submodular energies: Coupling edges in graph cuts

  2011cited by this paper
• A Class of Submodular Functions for Document Summarization

  2011cited by this paper
• A Unified Continuous Greedy Algorithm for Submodular Maximization

  2011influential reference
• Maximizing Non-Monotone Submodular Functions

  2011cited by this paper
• Multi-document Summarization via Budgeted Maximization of Submodular Functions

  2010cited by this paper
• Submodular maximization by simulated annealing

  2010cited by this paper
• Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints

  2009cited by this paper
• Revenue submodularity

  2009cited by this paper
• Symmetry and Approximability of Submodular Maximization Problems

  2009influential reference
• An Online Algorithm for Maximizing Submodular Functions

  2008cited by this paper
• Optimal marketing strategies over social networks

  2008cited by this paper
• Efficient Sensor Placement Optimization for Securing Large Water Distribution Networks

  2008cited by this paper
• Near-optimal Observation Selection using Submodular Functions

  2007cited by this paper
• Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e

  2006cited by this paper
• An efficient approximation for the Generalized Assignment Problem

  2006cited by this paper
• Tight approximation algorithms for maximum general assignment problems

  2006cited by this paper
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem

  2005cited by this paper
• Near-optimal Nonmyopic Value of Information in Graphical Models

  2005cited by this paper
• Near-optimal sensor placements in Gaussian processes

  2005cited by this paper
• Maximum matchings via Gaussian elimination

  2004cited by this paper
• Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?

  2004cited by this paper
• Maximizing the spread of influence through a social network

  2003cited by this paper
• Combinatorial optimization. Polyhedra and efficiency.

  2003cited by this paper
• Some optimal inapproximability results

  2001cited by this paper
• Combinatorial approximation algorithms for the maximum directed cut problem

  2001cited by this paper
• A 0.5-Approximation Algorithm for MAX DICUT with Given Sizes of Parts

  2001cited by this paper
• Approximation Algorithms for Maximization Problems Arising in Graph Partitioning

  2001cited by this paper
• Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images

  2001cited by this paper
• An Approximation Algorithm for Hypergraph Max k-Cut with Given Sizes of Parts

  1999cited by this paper
• An 0.828-approximation Algorithm for the Uncapacitated Facility Location Problem

  1999cited by this paper
• The Budgeted Maximum Coverage Problem

  1999cited by this paper
• Approximation Algorithms for Maximum Coverage and Max Cut with Given Sizes of Parts

  1999cited by this paper
• Gadgets, approximation, and linear programming

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

  1996cited by this paper
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

  1995cited by this paper
• Approximating the value of two power proof systems, with applications to MAX 2SAT and MAX DICUT

  1995cited by this paper
• Improved approximation algorithms for MAXk-CUT and MAX BISECTION

  1995cited by this paper
• Randomized Algorithms: Tail Inequalities

  1995cited by this paper
• Note--On "Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms"

  1979cited by this paper
• An analysis of approximations for maximizing submodular set functions—I

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

  1978cited by this paper
• On the Uncapacitated Location Problem

  1977cited by this paper
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms

  1977cited by this paper
• Reducibility Among Combinatorial Problems

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

  1969cited by this paper

• Bicriteria Algorithms for Submodular Cover with Partition and Fairness Constraints

  2026influential citation
• Group equality and equity in submodular maximization

  2026cites this paper
• Derivation Depth as an Information Metric: Axioms, Coding Theorems, and Storage--Computation Tradeoffs

  2026cites this paper
• Knowledge graph-aided Bayesian active learning for top-K genetic interaction discovery

  2025cites this paper
• COMRECGC: Global Graph Counterfactual Explainer through Common Recourse

  2025cites this paper
• Revisiting non-monotone regularized submodular maximization: bi-criteria and PASS approximations

  2025influential citation
• Max-Cut with Multiple Cardinality Constraints

  2025influential citation
• Fast approximation algorithm for non-monotone DR-submodular maximization under size constraint

  2025cites this paper
• New Results on a General Class of Minimum Norm Optimization Problems

  2025cites this paper
• Fixed-Parameter Tractable Submodular Maximization over a Matroid

  2025cites this paper
• An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale

  2025cites this paper
• Logarithmic Regret for Unconstrained Submodular Maximization Stochastic Bandit

  2024cites this paper
• A Semi-streaming Algorithm for Monotone Regularized Submodular Maximization with a Matroid Constraint

  2024cites this paper
• Evolving Reliable Differentiating Constraints for the Chance-constrained Maximum Coverage Problem

  2024cites this paper
• Submodular Maximization Approaches for Equitable Client Selection in Federated Learning

  2024cites this paper
• Equitable Client Selection in Federated Learning via Truncated Submodular Maximization

  2024cites this paper
• Algorithmically Fair Maximization of Multiple Submodular Objective Functions

  2024cites this paper
• Product Design Problems with Operational Constraints: Efficient Algorithms Within the EBA Framework

  2024cites this paper
• Differentially private submodular maximization with a cardinality constraint over the integer lattice

  2024cites this paper
• Randomized Greedy Methods for Weak Submodular Sensor Selection with Robustness Considerations

  2024cites this paper
• Discretely Beyond 1/e: Guided Combinatorial Algorithms for Submodular Maximization

  2024influential citation
• Separating Coverage and Submodular: Maximization Subject to a Cardinality Constraint

  2024cites this paper
• Fairness in Streaming Submodular Maximization Subject to a Knapsack Constraint

  2024cites this paper
• Efficient Deterministic Algorithms for Maximizing Symmetric Submodular Functions

  2024cites this paper
• Deterministic Algorithm and Faster Algorithm for Submodular Maximization Subject to a Matroid Constraint

  2024cites this paper
• LLMCO4MR: LLMs-Aided Neural Combinatorial Optimization for Ancient Manuscript Restoration from Fragments with Case Studies on Dunhuang

  2024cites this paper
• Localized Distributional Robustness in Submodular Multi-Task Subset Selection

  2024cites this paper
• Fine-grained recognition via submodular optimization regulated progressive training

  2024cites this paper
• Efficient Decision Rule List Learning via Unified Sequence Submodular Optimization

  2024cites this paper
• Deep Submodular Peripteral Networks

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

  2024cites this paper
• Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and More

  2024cites this paper
• The Power of Second Chance: Personalized Submodular Maximization with Two Candidates

  2024cites this paper
• Extending the Extension: Deterministic Algorithm for Non-monotone Submodular Maximization

  2024influential citation
• Practical 0.385-Approximation for Submodular Maximization Subject to a Cardinality Constraint

  2024influential citation
• Relative Entropy Regularization for Robust Submodular Multi-Task Subset Selection

  2023cites this paper
• INVALS: A Forward Looking Inventory Allocation System

  2023influential citation
• Fairness in Submodular Maximization over a Matroid Constraint

  2023influential citation
• On Data-Aware Global Explainability of Graph Neural Networks

  2023cites this paper
• Data Summarization beyond Monotonicity: Non-monotone Two-Stage Submodular Maximization

  2023cites this paper
• An EPTAS for Cardinality Constrained Multiple Knapsack via Iterative Randomized Rounding

  2023cites this paper
• SIGACT News Online Algorithms Column 41: 2023 in review

  2023cites this paper
• A Tight Competitive Ratio for Online Submodular Welfare Maximization

  2023influential citation
• Efficient Public Transport Planning on Roads

  2023cites this paper
• A Note on Maximizing Regularized Submodular Functions Under Streaming

  2023cites this paper
• Practical Parallel Algorithms for Non-Monotone Submodular Maximization

  2023cites this paper
• Towards One-shot Neural Combinatorial Solvers: Theoretical and Empirical Notes on the Cardinality-Constrained Case

  2023cites this paper
• Independent Sets in Elimination Graphs with a Submodular Objective

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

  2023influential citation
• Submodular Minimax Optimization: Finding Effective Sets

  2023cites this paper
• Constrained Subset Selection from Data Streams for Profit Maximization

  2023cites this paper
• Faster Submodular Maximization for Several Classes of Matroids

  2023cites this paper
• Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint

  2023cites this paper
• Non-monotone Sequential Submodular Maximization

  2023influential citation
• A Scalable Solution for the Extended Multi-channel Facility Location Problem

  2023cites this paper
• On the Approximability of External-Influence-Driven Problems

  2023cites this paper
• Assigning Agents to Increase Network-Based Neighborhood Diversity

  2023cites this paper
• Group fairness in non-monotone submodular maximization

  2023cites this paper
• High Probability Guarantees for Submodular Maximization via Boosted Stochastic Greedy

  2023cites this paper
• Bicriteria Approximation Algorithms for the Submodular Cover Problem

  2023cites this paper
• Constrained Submodular Maximization via New Bounds for DR-Submodular Functions

  2023cites this paper
• Dynamic Non-monotone Submodular Maximization

  2023cites this paper
• Submodular Maximization under the Intersection of Matroid and Knapsack Constraints

  2023influential citation
• Improved Algorithm for Regret Ratio Minimization in Multi-Objective Submodular Maximization

  2023cites this paper
• Beyond submodularity: a unified framework of randomized set selection with group fairness constraints

  2023influential citation
• Randomized Pricing with Deferred Acceptance for Revenue Maximization with Submodular Objectives

  2023cites this paper
• On Maximizing Sums of Non-monotone Submodular and Linear Functions

  2022cites this paper
• Submodular Maximization Subject to Matroid Intersection on the Fly

  2022cites this paper
• Efficient Algorithms for Monotone Non-Submodular Maximization with Partition Matroid Constraint

  2022cites this paper
• Greedy modality selection via approximate submodular maximization

  2022cites this paper
• Local search and swapping strategies. Challenging the greedy maximization of a polymatroid subject to a cardinality constraint

  2022cites this paper
• Using Partial Monotonicity in Submodular Maximization

  2022influential citation
• Lazy and Fast Greedy MAP Inference for Determinantal Point Process

  2022influential citation
• A survey on outlier explanations

  2022cites this paper
• Fair Incentive Mechanism With Imperfect Quality in Privacy-Preserving Crowdsensing

  2022cites this paper
• Towards Efficient and Domain-Agnostic Evasion Attack with High-dimensional Categorical Inputs

  2022cites this paper
• Nonmonontone submodular maximization under routing constraints

  2022cites this paper
• An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint

  2022influential citation
• Group Equality in Adaptive Submodular Maximization

  2022cites this paper
• Scalable Distributed Algorithms for Size-Constrained Submodular Maximization in the MapReduce and Adaptive Complexity Models

  2022cites this paper
• Progressive Training Enabled Fine-Grained Recognition

  2022cites this paper
• Deletion Robust Non-Monotone Submodular Maximization over Matroids

  2022influential citation
• Fair Assortment Planning

  2022influential citation
• Towards Understanding the Robustness Against Evasion Attack on Categorical Data

  2022cites this paper
• T OWARDS U NDERSTANDING THE R OBUSTNESS A GAINST E VASION A TTACK ON C ATEGORICAL I NPUTS

  2022cites this paper
• Learning Interpretable Decision Rule Sets: A Submodular Optimization Approach

  2022cites this paper
• Private non-monotone submodular maximization

  2022cites this paper
• Improved Deterministic Algorithms for Non-monotone Submodular Maximization

  2022influential citation
• Group Fairness in Adaptive Submodular Maximization

  2022influential citation
• Approximation Algorithms for Size-Constrained Non-Monotone Submodular Maximization in Deterministic Linear Time

  2021cites this paper
• Streaming Submodular Maximization Under Matroid Constraints

  2021influential citation
• A Tight Deterministic Algorithm for the Submodular Multiple Knapsack Problem

  2021cites this paper
• The Power of Randomization: Efficient and Effective Algorithms for Constrained Submodular Maximization

  2021influential citation
• On Submodular Prophet Inequalities and Correlation Gap

  2021influential citation
• Streaming Based Bicriteria Approximation Algorithms for Submodular Optimization

  2021cites this paper
• Local search and swapping strategies. Challenging the greedy outcome for the maximization of a polymatroid subject to a cardinality constraint

  2021cites this paper
• Greedy Bayesian Posterior Approximation with Deep Ensembles

  2021influential citation
• One-Round Active Learning

  2021cites this paper
• Finding High-Value Training Data Subset through Differentiable Convex Programming

  2021cites this paper
• A mobile multi-agent sensing problem with submodular functions under a partition matroid

  2021cites this paper