Data dependent worst case bounds for weighted set packing |
| |
| Institution: | 1. DEIO, Faculty of Sciences, University of Lisbon, Lisbon, Portugal.;2. Faculty of Sciences, Operations Research Center (CIO), University of Lisbon, Lisbon, Portugal.;3. ISCAC, Polytechnic Institute of Coimbra, Quinta Agrícola, Bencanta, 3040-316 , Coimbra, Portugal.;1. Department of Computer Science, University of Concepcion, Concepción, Chile;2. CeBiB — Center for Biotechnology and Bioengineering, Chile;3. Universidade da Coruña, Centro de investigación CITIC, A Coruña, Spain;4. IMFD — Millennium Institute for Foundational Research on Data, Chile;5. Department of Computer Science, University of Chile, Santiago, Chile;1. Amazon Inc., Tempe, AZ, USA;2. Depatment of Mathematics, University of Ioannina, Ioannina, Greece;3. Algorithms and Complexity Group, TU Wien, Vienna, Austria;4. Institut für Informatik, Universität Tübingen, Tübingen, Germany;5. Facebook, Inc., Menlo Park, CA, USA |
| |
| Abstract: | We develop data dependent worst case bounds for three simple greedy algorithms for the maximum weighted independent set problem applied to maximum weighted set packing. We exploit the property that the generated output will attain at least a certain weight. These weight quantities are a function of the individual weights corresponding to the vertices of the problem. By using an argument based on linear programming duality we develop a priori bounds that are a function of the minimum guaranteed weight quantities, the highest average reward for a ground item, and cardinality of the ground set. This extends the current bounds which are only a function of the maximum vertex degree in the associated conflict graph. Examples are given that show the benefits of incorporating this data dependent information into bounds. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
