Apakah cukup untuk kendala program linier untuk dipenuhi dalam harapan?

Dalam makalah ini, Randomized Primal-Dual analisis RANKING untuk Online Bipartite Matching , sementara membuktikan bahwa algoritma RANKING adalah -competitive, penulis menunjukkan bahwa dual tersebut layak dalam harapan (lihat Lemma 3 di halaman 5). Pertanyaanku adalah:$\left(1 - \frac{1}{e}\right)$

Apakah cukup untuk kendala program linier untuk dipenuhi dalam harapan?

Adalah satu hal untuk menunjukkan bahwa nilai yang diharapkan dari fungsi objektif adalah sesuatu. Tetapi jika kendala kelayakan dipenuhi dalam ekspektasi, tidak ada jaminan bahwa itu akan puas pada jangka yang diberikan. Apalagi ada banyak kendala seperti itu. Jadi apa jaminan bahwa SEMUA dari mereka akan puas pada jangka waktu tertentu?

Saya pikir kesulitannya adalah bahwa kata-kata ini sedikit menyesatkan; karena mereka menyatakan lebih jelas dalam Pendahuluan (1.2), "nilai-nilai yang diharapkan dari variabel ganda merupakan solusi ganda yang layak."

Untuk setiap pengaturan tetap dari variabel ganda , kami mendapatkan beberapa solusi primal dari nilai dan solusi ganda dari nilai . (Dual tidak mungkin dalam beberapa kasus ini, tapi tidak apa-apa.)$X$$f(X)$$\frac{e}{e-1}f(X)$

Jadi nilai yang diharapkan dari primal atas semua berjalan dari algoritma adalah . Tetapi adalah solusi dua-layak, jadi ada solusi ganda nilai . Trik kuncinya adalah bahwa adalah linear dalam variabel ganda : Faktanya, di sini variabel ganda adalah dan , dan setiap pencocokan simpul ke menambahkan total ke tujuan awal. Jadi dan kesimpulannya berikut.$E[f(X)]$$E[X]$$\frac{e}{e-1}f(E[X])$$f(X)$$X$$\alpha_i$$\beta_j$$i$$j$$\left(\frac{e-1}{e}\right)(\alpha_i + \beta_j)$$E[f(X)] = f(E[X])$

(Sebagai catatan, saya merasa bahwa, karena poin ini adalah salah satu fokus utama dari makalah mereka (menurut abstrak), akan lebih baik jika mereka menjelaskan poin ini! Tampaknya sama sekali tidak jelas bagi saya, dan saya ingin mencari tahu kapan itu benar secara umum.)