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

Previewing pages 1, 2, 3 of 10 page document
View Full Document

# CS 787 Lecture Notes

Previewing pages 1, 2, 3 of actual document.

View Full Document
View Full Document

## CS 787 Lecture Notes

78 views

Problems/Exams

Pages:
10
School:
Course:
• 7 pages

• 3 pages

• 9 pages

• 10 pages

• 6 pages

• 6 pages

• 4 pages

• 7 pages

• 6 pages

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

Unlocking...