Cover Image

Deterministic Algorithm for Non-monotone Submodular Maximization under Matroid and Knapsack Constraints

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chen, Shengminjie, Gao, Yiwei, Lin, Kaifeng, Sun, Xiaoming, Zhang, Jialin
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms Computational Complexity Optimization and Control
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Continuous Non-monotone DR-submodular Maximization with Down-closed Convex Constraint
by: Chen, Shengminjie, et al.
Published: (2023)

On the Distribution of Unweighted Minimum Knapsack Instances with Large SOS Rank
by: Kurpisz, Adam, et al.
Published: (2026)

Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity
by: Pham, Canh V.
Published: (2024)

Submodular Maximization under Supermodular Constraint: Greedy Guarantees
by: Srivastava, Ajitesh, et al.
Published: (2026)

Efficient Deterministic Algorithms for Maximizing Symmetric Submodular Functions
by: Wan, Zongqi, et al.
Published: (2024)

Solving convex QPs with structured sparsity under indicator conditions
by: Bienstock, Daniel, et al.
Published: (2024)

Centrality of shortest paths: Algorithms and complexity results
by: Phosavanh, Johnson, et al.
Published: (2024)

A Control-Theoretic Perspective on Optimal High-Order Optimization
by: Lin, Tianyi, et al.
Published: (2019)

A Continuous-Time Perspective on Global Acceleration for Monotone Equation Problems
by: Lin, Tianyi, et al.
Published: (2022)

A note on the complexity of the picker routing problem in multi-block warehouses and related problems
by: Prunet, Thibault, et al.
Published: (2023)

Maximization of Approximately Submodular Functions
by: Horel, Thibaut, et al.
Published: (2024)

Sum-Of-Squares To Approximate Knapsack
by: Kothari, Pravesh K., et al.
Published: (2025)

Algorithms for Standard-form ILP Problems via Komlós' Discrepancy Setting
by: Gribanov, Dmitry, et al.
Published: (2026)

Knapsack on Graphs with Relaxed Neighborhood Constraints
by: Dey, Palash, et al.
Published: (2025)

Algorithmically Fair Maximization of Multiple Submodular Objective Functions
by: Amanatidis, Georgios, et al.
Published: (2024)

Sparse Submodular Function Minimization
by: Graur, Andrei, et al.
Published: (2023)

Generalized Assignment and Knapsack Problems in the Random-Order Model
by: Klimm, Max, et al.
Published: (2025)

A 1/2-Approximation for Budgeted $k$-Submodular Maximization
by: Wang, Chenhao
Published: (2025)

Efficient Branch-and-Bound for Submodular Function Maximization under Knapsack Constraint
by: Hao, Yimin, et al.
Published: (2025)

Submodular Order Functions and Assortment Optimization
by: Udwani, Rajan
Published: (2021)

Cascading-Tree Algorithm for the 0-1 Knapsack Problem (In Memory of Heiner M{ü}ller-Merbach, a Former President of IFORS)
by: Moeini, Mahdi, et al.
Published: (2024)

ResQue Greedy: Rewiring Sequential Greedy for Improved Submodular Maximization
by: Gallart, Joan Vendrell, et al.
Published: (2025)

Fair Submodular Maximization over a Knapsack Constraint
by: Li, Lijun, et al.
Published: (2025)

Improved Algorithms for Fair Matroid Submodular Maximization
by: Mahabadi, Sepideh, et al.
Published: (2026)

Subquadratic Submodular Maximization with a General Matroid Constraint
by: Kobayashi, Yusuke, et al.
Published: (2024)

Fast Approximation Algorithm for Non-Monotone DR-submodular Maximization under Size Constraint
by: Tran, Tan D., et al.
Published: (2025)

Simultaneous Network Design with Restricted Link Usage
by: Kakimura, Naonori, et al.
Published: (2025)

Unifying Formal Explanations: A Complexity-Theoretic Perspective
by: Bassan, Shahaf, et al.
Published: (2026)

Semidefinite programming and linear equations vs. homomorphism problems
by: Ciardo, Lorenzo, et al.
Published: (2023)

Delta-modular ILP Problems of Bounded Codimension, Discrepancy, and Convolution (new version)
by: Cherniavskii, M., et al.
Published: (2024)

Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems
by: Blanchard, Moise
Published: (2024)

A degree 4 sum-of-squares lower bound for the clique number of the Paley graph
by: Kunisky, Dmitriy, et al.
Published: (2022)

Efficient Convex Optimization Requires Superlinear Memory
by: Marsden, Annie, et al.
Published: (2022)

A Unified Algorithmic Framework for Dynamic Assortment Optimization under MNL Choice
by: Sun, Shuo, et al.
Published: (2024)

Solving Linear Programs with Fast Online Learning Algorithms
by: Gao, Wenzhi, et al.
Published: (2021)

Removable Online Knapsack and Advice
by: Böckenhauer, Hans-Joachim, et al.
Published: (2020)

Competitive Online Optimization under Inventory Constraints
by: Lin, Qiulin, et al.
Published: (2019)

An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases
by: Khanna, Sanjeev, et al.
Published: (2026)

Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
by: Amanatidis, Georgios, et al.
Published: (2020)

Maximizing a Submodular Function with Bounded Curvature under an Unknown Knapsack Constraint
by: Klimm, Max, et al.
Published: (2022)