אלגוריתמים - קירוב לבעיית k המרכזים (Metric k-center)
ฝัง
- เผยแพร่เมื่อ 21 มิ.ย. 2024
- בעיית k-center, קשר לבעיית Domaining Set (קבוצה שולטת בגרף),
אלגוריתם 2-קירוב לבעיית k המרכזים (Metric k-center),
הוכחת Hardness of approximation לפקטור קטן מ2 (לא ניתן לקרב את הבעיה בפחות מ2 אלא אם P=NP).