Thuật Toán Xấp Xỉ cho Bài Toán K-Cắt Tối Thiểu

Cho G=(V,E) là một đồ thị hoàn chỉnh vô hướng, với tập đỉnh V={v_1, . . ., v_n} và tập cạnh E. Các cạnh (v_i,v_j) ∈ E có trọng số không âm và thỏa mãn bất đẳng thức tam giác. Cho một tập hợp các số nguyên K = { k_i } với i=1 đến p sao cho (\sum_{i=1}^p k_i \leq |V|), bài toán K-cắt tối thiểu là tìm các tập con không giao nhau với kích thước { k_i } sao cho tổng trọng số của các cạnh có hai đầu nằm trong các tập con khác nhau là nhỏ nhất. Chúng tôi chứng minh rằng đối với bất kỳ p cố định nào, có thể thu được một xấp xỉ trong thời gian đa thức với giá trị tối ưu tối đa gấp ba lần. Chúng tôi cũng chứng minh giới hạn về tỷ lệ giữa trọng số của cắt tối đa và tối thiểu.