Approximating the least core value and least core of cooperative games with supermodular costs
From MaRDI portal
Publication:2445844
DOI10.1016/j.disopt.2013.02.002zbMath1284.91034OpenAlexW2292516383MaRDI QIDQ2445844
Andreas S. Schulz, Nelson A. Uhan
Publication date: 15 April 2014
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disopt.2013.02.002
Cooperative games (91A12) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items
A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization ⋮ Streaming algorithm for maximizing a monotone non-submodular function under \(d\)-knapsack constraint ⋮ Two-stage non-submodular maximization ⋮ Two-stage BP maximization under \(p\)-matroid constraint ⋮ Two-stage non-submodular maximization ⋮ Computing Near-Optimal Stable Cost Allocations for Cooperative Games by Lagrangian Relaxation ⋮ Two-stage BP maximization under \(p\)-matroid constraint ⋮ Online algorithms for BP functions maximization ⋮ Coreness of cooperative games with truncated submodular profit functions ⋮ Online BP functions maximization ⋮ Two-stage submodular maximization under curvature ⋮ Simultaneous Penalization and Subsidization for Stabilizing Grand Cooperation ⋮ Online Submodular Maximization with Preemption ⋮ A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints ⋮ Improved algorithms for non-submodular function maximization problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Economic lot-sizing games
- Sequencing games
- An equivalence theorem for a bargaining set
- Traveling salesman games
- Geometric algorithms and combinatorial optimization
- On the least core and the Mas-Colell bargaining set
- Approximate strong separation with application in fractional graph coloring and preemptive scheduling.
- Note on the computational complexity of least core concepts for min-cost spanning tree games.
- On the computation of the nucleolus of a cooperative game
- A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem
- Cores of inventory centralization games
- Structure of a simple scheduling polyhedron
- A characterization of the Shapley value in queueing problems
- A primal-dual algorithm for computing a cost allocation in the core of economic lot-sizing games
- Cost sharing in a job scheduling problem
- Cores of convex games
- The assignment game. I: The core
- Tight Approximation Algorithms for Maximum Separable Assignment Problems
- Sharing Supermodular Costs
- On some approximately balanced combinatorial cooperative games
- Note on Independence Functions
- Efficient algorithms for a family of matroid intersection problems
- Geometric Properties of the Kernel, Nucleolus, and Related Solution Concepts
- Minimum cost spanning tree games
- Generalized Network Problems Yielding Totally Balanced Games
- Totally Balanced Games and Games of Flow
- On the core of linear production games
- Algorithms for Scheduling Independent Tasks
- On cost allocation for a spanning tree: A game theoretic approach
- An analysis of approximations for maximizing submodular set functions—I
- Computational Complexity of the Game Theory Approach to Cost Allocation for a Tree
- On the Complexity of Cooperative Solution Concepts
- Complexity of the Minimum Base Game on Matroids
- Randomized metarounding
- Scheduling independent tasks to reduce mean finishing time
- Cooperative facility location games
- Quasi-Cores in a Monetary Economy with Nonconvex Preferences
- The Nucleolus of a Characteristic Function Game
- Matroids and the greedy algorithm
- Matching Games: The Least Core and the Nucleolus