- Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency
2025/02/07 by Qixin Zhang, Zongqi Wan, Zhang, Qixin +7 · 2 citations
Computer Science · Engineering · Mathematics · #Artificial intelligence #Computer science #Distributed computing #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning and ELM #Mathematical optimization #Mathematics #Multiagent Systems (cs.MA) #Optimization and Control (math.OC) #Privacy-Preserving Technologies in Data #RFID technology advancements #Submodular set function #Theoretical computer science
- A Note on Isolating Cut Lemma for Submodular Function Minimization
2021/03/29 by Sagnik Mukhopadhyay, Mukhopadhyay, Sagnik, Danupon Nanongkai +1 · 3 citations
Computer Science · Mathematics · #Biology #Botany #Coding theory and cryptography #Combinatorics #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Function (biology) #Lemma (botany) #Mathematical optimization #Mathematics #Minification #Submodular set function #cs.DS
- Overcommitment in Cloud Services: Bin Packing with Chance Constraints
2019/01/28 by Maxime C. Cohen, Philipp W. Keller, Vahab Mirrokni +1 · 1 citation
Computer Science · Engineering · Mathematics · #Optimization and Search Problems #Cloud Computing and Resource Management #Optimization and Packing Problems #Computer science #Submodular set function #Cloud computing #Pooling #Workload #Bin packing problem #Scheduling (production processes) #Bin #Operations research #Mathematical optimization #Artificial intelligence #Algorithm #Mathematics
- Approximation and complexity of the optimization and existence problems for maximin share, proportional share, and minimax share allocation of indivisible goods
2018/06/26 by Tobias Heinen, Nhan-Tam Nguyen, Trung Thanh Nguyen +1 · 1 citation
Computer Science · Decision Sciences · Economics, Econometrics and Finance · Mathematics · #Auction Theory and Applications #Class (philosophy) #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Fair division #Game Theory and Voting Systems #Lexicographical order #Mathematical economics #Mathematical optimization #Mathematics #Minimax #Submodular set function
- Maximizing Monotone Submodular Functions over the Integer Lattice
2015/03/04 by Tasuku Soma, Soma, Tasuku, Yuichi Yoshida +1 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Approximation algorithm #Cardinality (data modeling) #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Constraint (computer-aided design) #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #Discrete mathematics #FOS: Computer and information sciences #Function (biology) #Integer (computer science) #Integer lattice #Knapsack problem #Lattice (music) #Mathematical optimization #Mathematics #Monotone polygon #Oracle #Submodular set function #cs.DS
- Submodular Function Maximization
2014/02/06 by Andreas Krause, Daniel Golovin · 4 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Machine Learning and Algorithms #Cryptography and Data Security #Submodular set function #Maximization #Function (biology) #Computer science #Mathematical optimization #Mathematics #Biology #Evolutionary biology
- Submodular Maximization with Cardinality Constraints
2013/12/18 by Niv Buchbinder, Moran Feldman, Joseph Naor +1 · 1 citation
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Advanced Graph Theory Research #Submodular set function #Cardinality (data modeling) #Monotone polygon #Approximation algorithm #Maximization #Range (aeronautics) #Constraint (computer-aided design) #Function (biology) #Greedy algorithm #Mathematical optimization #Computer science #Discrete mathematics #Mathematics #Combinatorics
- An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions
2013/01/01 by Thomas Kesselheim, Thomas Keßelheim, Klaus Radke +2 · 2 citations
Computer Science · Decision Sciences · Mathematics · #Algorithm #Auction Theory and Applications #Bipartite graph #Combinatorial auction #Combinatorial optimization #Combinatorics #Common value auction #Competitive analysis #Computer science #Cryptography and Data Security #Discrete mathematics #Graph #Hypergraph #Matching (statistics) #Mathematical optimization #Mathematics #Online algorithm #Optimization and Search Problems #Secretary problem #Submodular set function #Upper and lower bounds #Vertex (graph theory)
- Maximizing Non-monotone Submodular Set Functions Subject to Different\n Constraints: Combined Algorithms
2011/01/15 by Salman Fadaei, Fadaei, Salman, MohammadAmin Fazli +3 · 1 citation
Computer Science · Mathematics · #Algorithm #Approximation algorithm #Cardinality (data modeling) #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Constraint (computer-aided design) #Continuous knapsack problem #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #Discrete mathematics #FOS: Computer and information sciences #Function (biology) #Greedy algorithm #Knapsack problem #Mathematical optimization #Mathematics #Matroid #Maximization #Monotone polygon #Optimization and Search Problems #Polytope #Set (abstract data type) #Set function #Submodular set function #cs.DS
- Convex Analysis and Optimization with Submodular Functions: a Tutorial
2010/10/20 by Francis Bach, Bach, Francis · 1 citation
Computer Science · Engineering · Mathematics · #Complexity and Algorithms in Graphs #Computer science #Convex analysis #Convex function #Convex optimization #Digital Image Processing Techniques #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Mathematical optimization #Mathematics #Optimization and Control (math.OC) #Proper convex function #Regular polygon #Set (abstract data type) #Set function #Sparse and Compressive Sensing Techniques #Submodular set function #Theoretical computer science #cs.LG #math.OC #stat.ML
- Submodular Functions, Matroids, and Certain Polyhedra
2003/01/01 by Jack Edmonds · 5 citations
Computer Science · Mathematics · #Abstraction #Advanced Algebra and Logic #Algebra over a field #Algebraic number #Axiom #Cardinality (data modeling) #Combinatorics #Computer science #Geometry #Mathematics #Matroid #Oracle #Polyhedron #Programming language #Pure mathematics #Submodular set function #Van der Waerden's theorem
- A framework for cost-scaling algorithms for submodular flow problems
2002/12/30 by Harold N. Gabow · 1 citation
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Optimization and Search Problems #Minimum-cost flow problem #Orientation (vector space) #Submodular set function #Scaling #Flow network #Combinatorics #Mathematics #Upper and lower bounds #Vertex (graph theory) #Flow (mathematics) #Enhanced Data Rates for GSM Evolution #Approximation algorithm #Algorithm #Computer science #Graph #Geometry #Artificial intelligence
- Centroids, Representations, and Submodular Flows
1995/05/01 by H.N. Gabow, Harold N. Gabow · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Binary logarithm #Boundary (topology) #Centroid #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Computer science #Discrete mathematics #Geometry #Mathematics #Representation (politics) #Set (abstract data type) #Submodular set function #Tree (set theory)
- Forests, frames, and games: Algorithms for matroid sums and applications
1992/06/01 by Harold N. Gabow, Herbert Westermann, Herbert H. Westermann · 3 citations
Computer Science · Engineering · Mathematics · #Advanced Materials and Mechanics #Algorithm #Cardinality (data modeling) #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Discrete mathematics #Disjoint sets #Graphic matroid #Mathematics #Matroid #Matroid partitioning #Spanning tree #Structural Analysis and Optimization #Submodular set function #Theoretical computer science #Weighted matroid
- The structure of sperner k-families
1976/01/01 by Curtis Greene, Daniel J. Kleitman, Daniel J Kleitman · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Algebra and Logic #Class (philosophy) #Combinatorics #Computer science #Discrete mathematics #Extension (predicate logic) #Family of sets #Intersection (aeronautics) #Lattice (music) #Mathematics #Partially ordered set #Physics #Set (abstract data type) #Submodular set function #Transversal (combinatorics) #graph theory and CDMA systems #semigroups and automata theory