| |
|
การเขียนโปรแกรมเชิงเส้น เรขาคณิต บทตั้งของฟาร์กาส ภาวะคู่กันอย่างเข้ม ความซับซ้อน ขั้นตอนวิธี ทรงรี และการหาค่าที่เหมาะสมเทียบกับวิธีการแยก การขยายสู่โปรแกรมภาคตัดกรวย การไหลแบบเครือข่าย การไหลสูงสุด การไหลที่ค่าใช้จ่ายต่ำสุด ขั้นตอนวิธียกเลิกการวน การวิเคราะห์พหุนามเวลาอย่างเข้ม การตัดต่ำสุดโดยปราศจากการไหล ขั้นตอนวิธีประมาณการ ลิมิตถึงความสามารถในการประมาณการ เทคนิคพื้นฐาน และการครอบคลุมจุดยอด เทคนิคคู่เฉพาะ การเขียนโปรแกรมกึ่งแน่นอน การตัดหลายโภคภัณฑ์ด้วยการฝังตรึงไว้ในปริภูมิเมตริกช์ แผนการประมาณสำหรับยุคลิเดียนทีเอสพี โครงสร้างข้อมูล คิวแบบแวนเอ็มเดโบส แผนภูมิต้นไม้ขยายออก แผนภูมิต้นไม้พลวัติ
Linear programming: geometry, Farkas lemma, strong duality, complexity, ellipsoid algorithm and optimization vs. separation, extension to conic programming; network flows: maximum flows, min-cost flows, cycle canceling algorithms, strongly polynomial-time analysis, minimum cuts without flows; approximation algorithms: limits to approximability, basic techniques and vertex cover, primal-dual technique, semidefinite programming, multicommodity cut via embedding metric spaces, approximation scheme for Euclidean TSP; data structures: Van Emde Boas queues, splay trees, dynamic trees.
|
