دانلود گزارش کارورزی و کار آموزی

چکیده :

Inthisnote,wepresentasimplecombinatorialfactor6algorithmforapproximatingtheminimumhittingsetofafamilyR={R1,...,Rn}ofaxis-parallelrectanglesintheplanesuchthatthereexistsanaxis-monotonecurveγthatintersectseachrectangleinthefamily.Thequalityofthehittingsetisshownbycomparingittothesizeofapacking(setofpairwisenon-intersectingrectangles)thatisconstructedalong,hence,wealsoobtainafactor6approximationforthemaximumpackingofR.Incaseswheretheaxis-monotonecurveγintersectsthesameside(e.g.thebottomside)ofeachrectangleinthefamilytheapproximationfactorforhittingsetandpackingis3.