Complexity and Approximability of Optimal Resource Allocation and Nash Equilibrium over Networks
DOI10.1137/19M1242525zbMath1459.91069OpenAlexW3012140091MaRDI QIDQ5853723
No author found.
Publication date: 11 March 2021
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/19m1242525
computational complexityquadratic programmingapproximation algorithmresource allocationfacility locationpotential gamesnetwork gamesdata placement problem
Noncooperative games (91A10) Games involving graphs (91A43) Applications of game theory (91A80) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Potential and congestion games (91A14)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Price of anarchy and an approximation algorithm for the binary-preference capacitated selfish replication game
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
- A new approximation algorithm for the multilevel facility location problem
- Multiple criteria facility location problems: a survey
- Facility location and supply chain management. A review
- A 3-approximation algorithm for the \(k\)-level uncapacitated facility location problem
- Network formation and social coordination
- Potential games
- Global convergence of Rosen's gradient projection method
- A constant-factor approximation algorithm for the \(k\)-median problem
- On local search for the generalized graph coloring problem
- Congestion games with player-specific payoff functions
- A \(k\)-product uncapacitated facility location problem
- Placement Algorithms for Hierarchical Cooperative Caching
- Anti-coordination Games and Stable Graph Colorings
- Cache Me If You Can: Capacitated Selfish Replication Games
- Simple Local Search Problems that are Hard to Solve
- The Gradient Projection Method for Nonlinear Programming. Part I. Linear Constraints
- Approximation Algorithms for Data Placement Problems
- Approximation Algorithms for Metric Facility Location Problems
- On the impact of combinatorial structure on congestion games
- Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Set Partitioning via Inclusion-Exclusion
- The complexity of pure Nash equilibria
- Greedy Strikes Back: Improved Facility Location Algorithms
- Nonmonotone Spectral Projected Gradient Methods on Convex Sets
- Pure Nash Equilibrium in a Capacitated Selfish Resource Allocation Game
- Gradient projection methods for quadratic programs and applications in training support vector machines
- Selfish caching in distributed systems
- Scheduling to Minimize Interaction Cost
- Integer Programming and Combinatorial Optimization
This page was built for publication: Complexity and Approximability of Optimal Resource Allocation and Nash Equilibrium over Networks
