Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Một FPTAS để tối thiểu hóa sản phẩm của hai hàm chi phí tuyến tính không âm
Tóm tắt
Chúng tôi xem xét một bài toán lập trình bậc hai (QP) có dạng min x^T C x với điều kiện Ax ≥ b, x ≥ 0, trong đó C ∈ ℝ^{n × n}_+, {
m rank}(C)=1 và A ∈ ℝ^{m × n}, b ∈ ℝ^m. Chúng tôi trình bày một sơ đồ xấp xỉ thời gian đa thức hoàn toàn (FPTAS) cho bài toán này bằng cách tái định hình QP (Π) thành một bài toán LP có tham số và “làm tròn” giải pháp tối ưu. Hơn nữa, thuật toán của chúng tôi trả về giải pháp điểm cực cho đa diện. Do đó, kết quả của chúng tôi áp dụng trực tiếp cho các bài toán 0–1 mà trong đó bao hàm lồi của các giải pháp nguyên khả thi đã được biết như cây bao trùm, các cặp ghép và dòng phụ lồi. Chúng cũng áp dụng cho các bài toán mà trong đó bao hàm lồi của các giải pháp nguyên khả thi thống trị đã được biết như đường đi ngắn nhất từ s đến t và cắt tối thiểu từ s đến t. Đối với các bài toán rời rạc nêu trên, chương trình bậc hai Π mô hình hóa bài toán tìm kiếm một giải pháp nguyên tối thiểu hóa sản phẩm của hai hàm chi phí không âm tuyến tính.
Từ khóa
#Lập trình bậc hai #sơ đồ xấp xỉ thời gian đa thức hoàn toàn #hàm chi phí tuyến tính không âm #giải pháp điểm cực #bài toán 0–1.Tài liệu tham khảo
Boyd S., Vandenberghe L.: Convex Optimization. Cambridge University Press, Cambridge (2004)
Brønsted A.: An Introduction to Convex Polytopes. Graduate Texts in Mathematics, vol .90. Springer, New York (1983)
Gould, N., Toint, P.: A quadratic programming bibliography. Numer. Anal. Group Intern. Rep. 1 (2000)
Hassin R.: Approximation schemes for the restricted shortest path problem. Math. Oper. Res. 17(1), 36–42 (1992)
Kern W., Woeginger G.: Quadratic programming and combinatorial minimum weight product problems. Math. Programm. 110(3), 641–649 (2007)
Matsui T.: NP-hardness of linear multiplicative programming and related problems. J. Glob. Optim. 9(2), 113–119 (1996)
Pardalos P., Vavasis S.: Quadratic programming with one negative eigenvalue is NP-hard. J. Glob. Optim. 1(1), 15–22 (1991)
Ravi, R., Goemans, M.: The constrained minimum spanning tree problem. In: Proceedings of 5th Scandinavian Workshop on Algorithm Theory, Reykjavík, Iceland, 3–5 July 1996 (1996)
Vavasis S.: Approximation algorithms for indefinite quadratic programming. Math. Program. 57(1), 279–311 (1992)