Buchumschlag

Submodular Maximization under Supermodular Constraint: Greedy Guarantees

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Srivastava, Ajitesh, Teng, Shanghua
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Data Structures and Algorithms Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Maximization of Approximately Submodular Functions
von: Horel, Thibaut, et al.
Veröffentlicht: (2024)

Deterministic Algorithm for Non-monotone Submodular Maximization under Matroid and Knapsack Constraints
von: Chen, Shengminjie, et al.
Veröffentlicht: (2026)

Overcoming Non-Submodularity: Towards Constant Approximation for Network Immunization
von: Srivastava, Ajitesh, et al.
Veröffentlicht: (2024)

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

A Unified Approach to Submodular Maximization Under Noise
von: Bhawalkar, Kshipra, et al.
Veröffentlicht: (2025)

Self-referential instances of the dominating set problem are irreducible
von: Zhou, Guangyan
Veröffentlicht: (2026)

The Complexity of Maximal Common Subsequence Enumeration
von: Buzzega, Giovanni, et al.
Veröffentlicht: (2025)

Minimizing Envy and Maximizing Happiness in Graphical House Allocation
von: Dhar, Anubhav, et al.
Veröffentlicht: (2025)

Knapsack on Graphs with Relaxed Neighborhood Constraints
von: Dey, Palash, et al.
Veröffentlicht: (2025)

A Threshold Greedy Algorithm for Noisy Submodular Maximization
von: Chen, Wenjing, et al.
Veröffentlicht: (2023)

Search-space Reduction for Boolean MinCSPs via Essential Constraints
von: Jansen, Bart M. P., et al.
Veröffentlicht: (2026)

Broadcasting under Structural Restrictions
von: Egami, Yudai, et al.
Veröffentlicht: (2025)

Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study
von: Bai, Tian, et al.
Veröffentlicht: (2026)

Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic
von: Mao, Songtao
Veröffentlicht: (2026)

Active Learning for Decision Trees with Provable Guarantees
von: Moakhar, Arshia Soltani, et al.
Veröffentlicht: (2026)

Vector TSP: A Traveling Salesperson Problem with Racetrack-like Acceleration Constraints
von: Casteigts, Arnaud, et al.
Veröffentlicht: (2020)

List Decoding Expander-Based Codes up to Capacity in Near-Linear Time
von: Srivastava, Shashank, et al.
Veröffentlicht: (2025)

Efficient Branch-and-Bound for Submodular Function Maximization under Knapsack Constraint
von: Hao, Yimin, et al.
Veröffentlicht: (2025)

Complexity of Constructing Minimal Faithful Permutation Representations for Fitting-free Groups
von: Levet, Michael, et al.
Veröffentlicht: (2025)

Random tensor isomorphism under orthogonal and unitary actions
von: Chizewer, Jeremy, et al.
Veröffentlicht: (2026)

Parallel Complexity of Depth-First-Search and Maximal path in restricted graph classes
von: Chauhan, Archit, et al.
Veröffentlicht: (2025)

Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions
von: Chen, Yixin, et al.
Veröffentlicht: (2026)

Second Price Matching with Complete Allocation and Degree Constraints
von: Pinchasi, Rom, et al.
Veröffentlicht: (2025)

On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems
von: DeHaan, Ian, et al.
Veröffentlicht: (2025)

Subquadratic Submodular Maximization with a General Matroid Constraint
von: Kobayashi, Yusuke, et al.
Veröffentlicht: (2024)

Improved Evolutionary Algorithms for Submodular Maximization with Cost Constraints
von: Zhu, Yanhui, et al.
Veröffentlicht: (2024)

Fair Submodular Maximization over a Knapsack Constraint
von: Li, Lijun, et al.
Veröffentlicht: (2025)

Neighborhood-Aware Graph Labeling Problem
von: Shahverdikondori, Mohammad, et al.
Veröffentlicht: (2026)

Lazy Kronecker Product
von: Song, Zhao
Veröffentlicht: (2026)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
von: Nederlof, Jesper
Veröffentlicht: (2026)

Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
von: Jiang, Cheng, et al.
Veröffentlicht: (2026)

A fine-grained dichotomy for the center problem on Gromov hyperbolic graphs
von: Ducoffe, Guillaume
Veröffentlicht: (2026)

Automated Lower Bounds for Small Matrix Multiplication Complexity over Finite Fields
von: Wang, Chengu
Veröffentlicht: (2026)

Polynomial-Time Almost Log-Space Tree Evaluation by Catalytic Pebbling
von: Asadi, Vahid R., et al.
Veröffentlicht: (2026)

NP-Hardness and a PTAS for the Pinwheel Problem
von: Kleinberg, Robert, et al.
Veröffentlicht: (2026)

The Parameterized Complexity of Scheduling with Precedence Delays: Shuffle Product and Directed Bandwidth
von: Bodlaender, Hans L., et al.
Veröffentlicht: (2026)

Online Orthogonal Vectors Revisited
von: Gajulapalli, Karthik, et al.
Veröffentlicht: (2026)

Characterizing Streaming Decidability of CSPs via Non-Redundancy
von: Sharma, Amatya, et al.
Veröffentlicht: (2026)

The Mystery Deepens: On the Query Complexity of Tarski Fixed Points
von: Chen, Xi, et al.
Veröffentlicht: (2026)

Sublinear-query relative-error testing of halfspaces
von: Chen, Xi, et al.
Veröffentlicht: (2026)