ปัญหาการครอบคลุมสูงสุดเป็นคำถามคลาสสิกในวิทยาการคอมพิวเตอร์ทฤษฎีความซับซ้อนของการคำนวณและการวิจัยเชิงปฏิบัติการเป็นปัญหาที่สอนกันอย่างแพร่หลายในอัลกอริธึมการประมาณค่า

คุณจะได้รับเซตหลายชุดและตัวเลขหนึ่งตัวเป็นข้อมูลป้อนเข้าเซตเหล่านั้นอาจมีสมาชิกบางส่วนที่เหมือนกัน คุณต้องเลือกเซตไม่เกินจำนวนหนึ่ง โดยให้เซตที่เลือกมีจำนวนสมาชิกมากที่สุดเท่าที่จะเป็นไปได้ กล่าวคือ ผลรวมของเซตที่เลือกมีขนาดมากที่สุด ${\displaystyle k}$${\displaystyle k}$

ตามหลักการแล้ว ความคุ้มครองสูงสุด (แบบไม่ถ่วงน้ำหนัก)

ตัวอย่าง: ตัวเลขและกลุ่มของเซต${\displaystyle k}$${\displaystyle S=\{S_{1},S_{2},\ldots ,S_{m}\}}$

วัตถุประสงค์: ค้นหาสับเซตของเซตต่างๆ โดยที่และจำนวนองค์ประกอบที่ครอบคลุมมีค่าสูงสุด${\displaystyle S'\subseteq S}$${\displaystyle \left|S'\right|\leq k}$${\displaystyle \left|\bigcup _{S_{i}\in S'}{S_{i}}\right|}$

ปัญหาการครอบคลุมสูงสุดเป็นปัญหาNP-hardและไม่สามารถประมาณค่าได้ภายในภายใต้สมมติฐานมาตรฐาน ผลลัพธ์นี้ตรงกับอัตราส่วนการประมาณค่าที่ได้จากอัลกอริทึมโลภทั่วไปที่ใช้สำหรับ การเพิ่มค่าสูงสุดของฟังก์ชันย่อยโมดูลาร์ที่มีข้อจำกัดจำนวนสมาชิก^{[ 1 ]}${\displaystyle 1-{\frac {1}{e}}+o(1)\approx 0.632}$

ปัญหาการครอบคลุมสูงสุดสามารถกำหนดได้เป็นโปรแกรมเชิงเส้นจำนวนเต็ม ดังต่อไป นี้

เพิ่มสูงสุด	${\displaystyle \sum _{e_{j}\in E}y_{j}}$	(เพิ่มผลรวมขององค์ประกอบที่ครอบคลุมให้สูงสุด)
ขึ้นอยู่กับ	${\displaystyle \sum {x_{i}}\leq k}$	(เลือกได้ไม่เกินจำนวนชุดที่กำหนด) ${\displaystyle k}$
	${\displaystyle \sum _{e_{j}\in S_{i}}x_{i}\geq y_{j}}$	(หาก มีการเลือก อย่างน้อยหนึ่งชุด) ${\displaystyle y_{j}>0}$${\displaystyle e_{j}\in S_{i}}$
	${\displaystyle y_{j}\in \{0,1\}}$	(ถ้าหาก ได้รับความคุ้มครอง แล้ว) ${\displaystyle y_{j}=1}$${\displaystyle e_{j}}$
	${\displaystyle x_{i}\in \{0,1\}}$	(หากเลือกให้เป็นภาพปก )${\displaystyle x_{i}=1}$${\displaystyle S_{i}}$

อัลกอริทึมแบบโลภสำหรับการครอบคลุมสูงสุดจะเลือกเซตตามกฎข้อเดียว: ในแต่ละขั้นตอน ให้เลือกเซตที่มีจำนวนองค์ประกอบที่ยังไม่ถูกครอบคลุมมากที่สุด สามารถแสดงได้ว่าอัลกอริทึมนี้บรรลุอัตราส่วนการประมาณค่าของ[ ^{2 ] ผลลัพธ์}การประมาณค่าแบบ ln แสดงให้เห็นว่าอัลกอริทึมแบบโลภเป็นอัลกอริทึมการประมาณค่าแบบพหุนามที่ดีที่สุดสำหรับการครอบคลุมสูงสุดเว้นแต่^{[ 3 ]}${\displaystyle 1-{\frac {1}{e}}}$${\displaystyle P=NP}$

ผลลัพธ์เรื่องความไม่สามารถประมาณค่าได้นั้นใช้ได้กับส่วนขยายทั้งหมดของปัญหาการครอบคลุมสูงสุด เนื่องจากผลลัพธ์เหล่านี้ถือว่าปัญหาการครอบคลุมสูงสุดเป็นกรณีพิเศษ

ปัญหาการครอบคลุมสูงสุดสามารถนำไปใช้กับสถานการณ์การจราจรบนท้องถนนได้ ตัวอย่างหนึ่งคือการเลือกเส้นทางรถประจำทางในเครือข่ายขนส่งสาธารณะที่จะติดตั้งเครื่องตรวจจับหลุมบ่อเพื่อให้ครอบคลุมสูงสุด เมื่อมีเซ็นเซอร์จำนวนจำกัด ปัญหานี้เป็นส่วนขยายที่รู้จักกันดีของปัญหาการครอบคลุมสูงสุด และได้รับการสำรวจครั้งแรกในเอกสารโดย Junade Ali และ Vladimir Dyo ^{[ 4 ]}

ในเวอร์ชันที่มีการถ่วงน้ำหนัก ทุกองค์ประกอบจะมีน้ำหนัก งานคือการหาค่าความครอบคลุมสูงสุดซึ่งมีน้ำหนักสูงสุด เวอร์ชันพื้นฐานเป็นกรณีพิเศษเมื่อน้ำหนักทั้งหมดเป็นศูนย์ ${\displaystyle e_{j}}$${\displaystyle w(e_{j})}$${\displaystyle 1}$

เพิ่มค่าสูงสุด(เพิ่มค่าผลรวมถ่วงน้ำหนักขององค์ประกอบที่ครอบคลุมให้สูงสุด)${\displaystyle \sum _{e\in E}w(e_{j})\cdot y_{j}}$

ขึ้นอยู่กับเงื่อนไข (เลือกไม่เกินจำนวนชุดที่กำหนด) ${\displaystyle \sum {x_{i}}\leq k}$${\displaystyle k}$

${\displaystyle \sum _{e_{j}\in S_{i}}x_{i}\geq y_{j}}$(ถ้า มีการเลือก อย่างน้อยหนึ่งชุด)${\displaystyle y_{j}>0}$${\displaystyle e_{j}\in S_{i}}$

${\displaystyle y_{j}\in \{0,1\}}$(ถ้า หาก ครอบคลุมแล้ว )${\displaystyle y_{j}=1}$${\displaystyle e_{j}}$

${\displaystyle x_{i}\in \{0,1\}}$(หากเลือกให้เป็นภาพปก)${\displaystyle x_{i}=1}$${\displaystyle S_{i}}$

อัลกอริทึมโลภสำหรับการครอบคลุมสูงสุดแบบถ่วงน้ำหนักในแต่ละขั้นตอนจะเลือกชุดที่มีน้ำหนักสูงสุดขององค์ประกอบที่ไม่ถูกครอบคลุม อัลกอริทึมนี้บรรลุอัตราส่วนการประมาณค่าของ^{[ 1 ]}${\displaystyle 1-{\frac {1}{e}}}$

ในเวอร์ชันที่มีงบประมาณจำกัดและครอบคลุมสูงสุดนั้น ไม่เพียงแต่ทุกองค์ประกอบจะมีน้ำหนักเท่านั้น แต่ทุกชุดยังมีต้นทุน อีกด้วย แทนที่จะจำกัดจำนวนชุดในความคุ้มครองจะมีการกำหนดงบประมาณให้ งบประมาณนี้จะจำกัดต้นทุนรวมของความคุ้มครองที่สามารถเลือกได้ ${\displaystyle e_{j}}$${\displaystyle w(e_{j})}$${\displaystyle S_{i}}$${\displaystyle c(S_{i})}$${\displaystyle k}$${\displaystyle B}$${\displaystyle B}$

เพิ่มค่าสูงสุด(เพิ่มค่าผลรวมถ่วงน้ำหนักขององค์ประกอบที่ครอบคลุมให้สูงสุด)${\displaystyle \sum _{e\in E}w(e_{j})\cdot y_{j}}$

ทั้งนี้ขึ้นอยู่กับเงื่อนไข (ราคาของชุดที่เลือกต้องไม่เกิน) ${\displaystyle \sum {c(S_{i})\cdot x_{i}}\leq B}$${\displaystyle B}$

${\displaystyle \sum _{e_{j}\in S_{i}}x_{i}\geq y_{j}}$(ถ้า มีการเลือก อย่างน้อยหนึ่งชุด)${\displaystyle y_{j}>0}$${\displaystyle e_{j}\in S_{i}}$

${\displaystyle y_{j}\in \{0,1\}}$(ถ้า หาก ครอบคลุมแล้ว )${\displaystyle y_{j}=1}$${\displaystyle e_{j}}$

${\displaystyle x_{i}\in \{0,1\}}$(หากเลือกให้เป็นภาพปก)${\displaystyle x_{i}=1}$${\displaystyle S_{i}}$

อัลกอริทึมแบบโลภจะไม่สร้างโซลูชันที่มีการรับประกันประสิทธิภาพอีกต่อไป กล่าวคือ พฤติกรรมกรณีที่เลวร้ายที่สุดของอัลกอริทึมนี้อาจอยู่ห่างไกลจากโซลูชันที่เหมาะสมที่สุดมาก อัลกอริทึมการประมาณค่าได้รับการขยายโดยวิธีต่อไปนี้ ขั้นแรก กำหนดอัลกอริทึมแบบโลภที่แก้ไขแล้ว ซึ่งจะเลือกเซตที่มีอัตราส่วนที่ดีที่สุดขององค์ประกอบที่ไม่ได้ครอบคลุมที่มีน้ำหนักต่อต้นทุน ประการที่สอง ในบรรดาการครอบคลุมที่มีขนาดให้หาการครอบคลุมที่ดีที่สุดที่ไม่ละเมิดงบประมาณ เรียกการครอบคลุมนี้ว่า ประการที่สาม หาการครอบคลุมทั้งหมด ที่มีขนาด ที่ไม่ละเมิดงบประมาณ โดยใช้การครอบคลุมที่มีขนาด เหล่านี้เป็นจุดเริ่มต้น ใช้อัลกอริทึมแบบโลภที่แก้ไขแล้ว โดยรักษาการครอบคลุมที่ดีที่สุดที่พบจนถึงปัจจุบัน เรียกการครอบคลุมนี้ว่าในตอนท้ายของกระบวนการ การครอบคลุมที่ดีที่สุดโดยประมาณจะเป็นหรืออัลกอริทึมนี้บรรลุอัตราส่วนการประมาณค่าสำหรับค่า ของนี่คืออัตราส่วนการประมาณค่าที่ดีที่สุดที่เป็นไปได้เว้นแต่^{[ 5 ]}${\displaystyle S_{i}}$${\displaystyle 1,2,...,k-1}$${\displaystyle H_{1}}$${\displaystyle k}$${\displaystyle k}$${\displaystyle H_{2}}$${\displaystyle H_{1}}$${\displaystyle H_{2}}$${\displaystyle 1-{1 \over e}}$${\displaystyle k\geq 3}$${\displaystyle NP\subseteq DTIME(n^{O(\log \log n)})}$

ในเวอร์ชันการครอบคลุมสูงสุดแบบทั่วไป แต่ละเซตจะมีต้นทุนและองค์ประกอบจะมีน้ำหนักและต้นทุนที่แตกต่างกันไป ขึ้นอยู่กับว่าเซตใดครอบคลุมมัน กล่าวคือ ถ้าถูกครอบคลุมโดยเซตน้ำหนักของ จะเป็นและต้นทุนจะเป็น มีการกำหนด งบประมาณสำหรับต้นทุนรวมของวิธีแก้ปัญหา ${\displaystyle S_{i}}$${\displaystyle c(S_{i})}$${\displaystyle e_{j}}$${\displaystyle e_{j}}$${\displaystyle S_{i}}$${\displaystyle e_{j}}$${\displaystyle w_{i}(e_{j})}$${\displaystyle c_{i}(e_{j})}$${\displaystyle B}$

เพิ่มค่าสูงสุด(โดยเพิ่มค่าสูงสุดของผลรวมถ่วงน้ำหนักขององค์ประกอบที่ครอบคลุมในเซตที่องค์ประกอบเหล่านั้นครอบคลุม)${\displaystyle \sum _{e\in E,S_{i}}w_{i}(e_{j})\cdot y_{ij}}$

ทั้งนี้ขึ้นอยู่กับเงื่อนไข (ราคาของชุดที่เลือกต้องไม่เกิน) ${\displaystyle \sum {c_{i}(e_{j})\cdot y_{ij}}+\sum {c(S_{i})\cdot x_{i}}\leq B}$${\displaystyle B}$

${\displaystyle \sum _{i}y_{ij}\leq 1}$(องค์ประกอบสามารถถูกครอบคลุมได้มากที่สุดเพียงชุดเดียวเท่านั้น)${\displaystyle e_{j}=1}$

${\displaystyle \sum _{S_{i}}x_{i}\geq y_{ij}}$(ถ้า มีการเลือก อย่างน้อยหนึ่งชุด)${\displaystyle y_{j}>0}$${\displaystyle e_{j}\in S_{i}}$

${\displaystyle y_{ij}\in \{0,1\}}$(ถ้าเช่นนั้นจะถูกครอบคลุมโดยเซต)${\displaystyle y_{ij}=1}$${\displaystyle e_{j}}$${\displaystyle S_{i}}$

${\displaystyle x_{i}\in \{0,1\}}$(หากเลือกให้เป็นภาพปก)${\displaystyle x_{i}=1}$${\displaystyle S_{i}}$

อัลกอริทึมนี้ใช้แนวคิดของต้นทุน/น้ำหนักส่วนเหลือ ต้นทุน/น้ำหนักส่วนเหลือจะวัดเทียบกับวิธีแก้ปัญหาชั่วคราว และเป็นผลต่างระหว่างต้นทุน/น้ำหนักส่วนเหลือกับต้นทุน/น้ำหนักส่วนเหลือที่ได้จากวิธีแก้ปัญหาชั่วคราว

อัลกอริทึมนี้มีหลายขั้นตอน ขั้นแรก ค้นหาวิธีแก้ปัญหาโดยใช้อัลกอริทึมแบบโลภ ในแต่ละรอบของอัลกอริทึมแบบโลภ วิธีแก้ปัญหาชั่วคราวจะถูกเพิ่มเข้าไปในเซตที่มีน้ำหนักคงเหลือสูงสุดขององค์ประกอบหารด้วยต้นทุนคงเหลือขององค์ประกอบเหล่านี้ พร้อมกับต้นทุนคงเหลือของเซต ขั้นที่สอง เปรียบเทียบวิธีแก้ปัญหาที่ได้จากขั้นตอนแรกกับวิธีแก้ปัญหาที่ดีที่สุดซึ่งใช้เซตจำนวนน้อย ขั้นที่สาม ส่งคืนวิธีแก้ปัญหาที่ดีที่สุดจากวิธีแก้ปัญหาทั้งหมดที่ตรวจสอบ อัลกอริทึมนี้บรรลุอัตราส่วนการประมาณค่าของ^{[ 6 ]}${\displaystyle 1-1/eo(1)}$

• ปัญหาการหาเซตที่ครอบคลุมคือการหาเซตที่ครอบคลุมองค์ประกอบทั้งหมดโดยใช้จำนวนเซตให้น้อยที่สุด