Greedy Heuristics for Client Assignment Problem by Zones

The Client Assignment Problem is an NP-hard problem applicable to online games in which a set of clients must be satisfactorily assigned to a subset of all available servers subject to various criteria. One particular variant of that problem we have defined as Offline CAP-Z separates the game world into zones and calls for heuristics to assign zones to servers such that a minimum fraction of players achieves a connection speed faster than a threshold of game quality known as QoS. We develop novel heuristics based on bin packing to find assignments much faster than previous solutions to CAP-Z while using a comparable number of servers.