On Local Search for Weighted k-Set Packing

References

• Bafna V., Narayanan B., Ravi R. Nonoverlapping local alignments (weighted independent sets of axis parallel rectangles). Proc. Workshop for Algorithms Data Structures (WADS) (1995) (Springer Verlag, New York) . LNCS 955Crossref, Google Scholar
• Cornuéjols G., Hartvigsen D. An extension of matching theory. J. Combin. Theory Ser. B (1986) 40:285–296Crossref, Google Scholar
• Cornuéjols G., Hartvigsen D., Pulleyblank W. Packing subgraphs in a graph. Oper. Res. Lett. (1982) 1:139–143Crossref, Google Scholar
• Crescenzi P., Kann V.A compendium of NP optimization problems (1997) . http://www.nada.kth.se/nada/theory/problemlist.htmlGoogle Scholar
• Duh R., Fürer M. Approximation of k-set cover by semi-local optimization. Proc. 29th Annual ACM Sympos. Theory Comput. (STOC) (1997) 256–264Crossref, Google Scholar
• Feo T., Goldschmidt O., Khellaf M. One-half approximation for the k-partition problem. Oper. Res. (1992) 40:S170–S172Link, Google Scholar
• Grable D. A. On random greedy triangle packing. Electronic J. Combin. (1997) 4(R11):19Google Scholar
• Halldórsson M. M. Approximating discrete collections via local improvements. Proc. 6th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (1995) 160–169Google Scholar
• Halldórsson M. M. Approximating k-set cover and complementary graph coloring. Proc. 5th Conf. Integer Programming and Combin. Optim. (IPCO) (1996) Crossref, Google Scholar
• Hurkens C. A. J., Schrijver A. On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems. SIAM J. Discrete Math. (1989) 2:68–72Crossref, Google Scholar
• Khanna S., Motwani R., Sudan M., Vazirani U. On syntactic versus computational views of approximability. Proc. 35th Annual IEEE Sympos. Foundations of Computer Science (FOCS) (1994) 819–830Crossref, Google Scholar