Please use this identifier to cite or link to this item: http://hdl.handle.net/10603/335652
Full metadata record
DC FieldValueLanguage
dc.coverage.spatial
dc.date.accessioned2021-08-10T11:48:55Z-
dc.date.available2021-08-10T11:48:55Z-
dc.identifier.urihttp://hdl.handle.net/10603/335652-
dc.description.abstractThe problem of locating facilities or resources within a specified region is one of the most well researched problems in the field of optimization and operations research. The problem is to identify an optimal set of locations (sites) to open facilities (warehouses) amongst a set of candidate locations, while minimizing the sum of the cost of installing (opening) the facilities plus the cost of allocating (assigning) request nodes (demand nodes) to open facilities. The assignment cost is generally the weighted sum of distances (Euclidean) between request nodes and facilities. Each facility also satisfies minimum or maximum capacity constraints. The most popular variant of facility location problem is the k-median problem. The k-median problem tries to minimize the allocation cost and allows at most k facilities to open or locate. Both FLP and k-median have been used in a wide range of applications including network design, data warehousing, and clustering to name a few. These are NP-hard problems, and have been extensively researched from the perspective of computational complexity i.e. average-case and worst-case performance guarantees. Such problems can be solved by using approximation algorithms. The approximation algorithms obtain a near optimal solution with the help of heuristics and techniques which include local search, linear programming rounding, and primal-dual algorithms. In this thesis, we have developed improved approximation algorithms for different variants of facility location problems. The algorithms we design are mainly based on two approximation techniques: linear programming rounding and the primal-dual approximation. We show that these techniques are very effective in solving variety of location-allocation problems.
dc.format.extent113p.
dc.languageEnglish
dc.relation
dc.rightsuniversity
dc.titleImproved Approximation Algorithms for Facility Location Problems
dc.title.alternative
dc.creator.researcherMehta, Vaishali
dc.subject.keywordApproximation Algorithms
dc.subject.keywordFacility location problems
dc.subject.keywordLinear programming
dc.description.note
dc.contributor.guideGarg, Deepak
dc.publisher.placePatiala
dc.publisher.universityThapar Institute of Engineering and Technology
dc.publisher.institutionDepartment of Computer Science and Engineering
dc.date.registered
dc.date.completed2018
dc.date.awarded
dc.format.dimensions
dc.format.accompanyingmaterialNone
dc.source.universityUniversity
dc.type.degreePh.D.
Appears in Departments:Department of Computer Science and Engineering

Files in This Item:
File Description SizeFormat 
01_title.pdfAttached File197.44 kBAdobe PDFView/Open
02_dedication.pdf117.38 kBAdobe PDFView/Open
03_table of contents.pdf491.31 kBAdobe PDFView/Open
04_certificate.pdf259.83 kBAdobe PDFView/Open
05_candidates declaration.pdf240.37 kBAdobe PDFView/Open
06_acknowledgement.pdf233.71 kBAdobe PDFView/Open
07_list of figures.pdf118.38 kBAdobe PDFView/Open
08_list of algorithms.pdf227.75 kBAdobe PDFView/Open
09_list of abbreviations.pdf117.37 kBAdobe PDFView/Open
10_list of publications.pdf303.33 kBAdobe PDFView/Open
11_abstract.pdf414.57 kBAdobe PDFView/Open
12_chapter 1.pdf783.17 kBAdobe PDFView/Open
13_chapter 2.pdf628.61 kBAdobe PDFView/Open
14_chapter 3.pdf831.33 kBAdobe PDFView/Open
15_chapter 4.pdf781.61 kBAdobe PDFView/Open
16_chapter 5.pdf648.14 kBAdobe PDFView/Open
17_chapter 6.pdf522.03 kBAdobe PDFView/Open
18_references.pdf357.77 kBAdobe PDFView/Open
80_recommendation.pdf611.15 kBAdobe PDFView/Open


Items in Shodhganga are licensed under Creative Commons Licence Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0).

Altmetric Badge: