UW-Madison COMPSCI 787 - CS 787 Lecture Notes (10 pages)

Previewing pages 1, 2, 3 of 10 page document View the full content.
View Full Document

CS 787 Lecture Notes



Previewing pages 1, 2, 3 of actual document.

View the full content.
View Full Document
View Full Document

CS 787 Lecture Notes

78 views

Problems/Exams


Pages:
10
School:
University of Wisconsin, Madison
Course:
Compsci 787 - Advanced Algorithms

Unformatted text preview:

CS787 Advanced Algorithms Topic Local Search Algorithms Presenter s Theodora Hinkle Ning Zhang In this note we will survey the local search heuristics for the metric k median and facility location problems We define the locality gap of a local search heuristics for a minimization problem as the maximum ratio of local optimal solution produced by local search heuristics to the global optimal solution For k median the local search with single swap has a locality gap of 5 Moreover if we allow p facilities to be swapped simultaneously the locality gap will be 3 p2 For uncapacitated facility location the local search which permits adding dropping and swapping a facility has a locality gap of 3 All above results are currently the best ones by using local search heuristics 17 2 1 Introduction 17 2 1 1 Background for k median and facility location problems Facility location problems capture a common need of many real world businesses to decide where to locate their facilities in a way that most effectively serves their clients Many aspects of the real world problem make finding solutions difficult and even the simplified models of metric k median and metric uncapacitated facility location are hard problems A facility location problem generally has a set of possible facility locations and a set of clients to be served There can be distances defined between the clients and facilities leading to a measure of effectiveness of a solution can vary depending on the service cost the distance between clients and the facilities they are assigned to in the solution There can also be unequal costs to opening different facilities leading to a measure of effectiveness depending on the facility cost the total cost to open the facilities chosen by a solution Using various combinations of these two measures as objective functions to be minimized leads to interesting problems In metric k median the number of facilities which may be open is at most k and the total service cost to all clients



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view CS 787 Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view CS 787 Lecture Notes and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?