Set disjoint maksimum: apa faktor perkiraan sebenarnya dari algoritma serakah?

Pertimbangkan masalah menemukan set disjoint maksimum - set maksimum bentuk geometris yang tidak tumpang tindih, dari koleksi kandidat tertentu. Ini adalah masalah NP-complete, tetapi dalam banyak kasus, algoritma serakah berikut menghasilkan perkiraan faktor konstan:

• Untuk setiap bentuk kandidat x , hitung angka perpotongan disjointnya = jumlah terbesar dari bentuk disjoint yang berpotongan x .$DIN(x)$
• Pilih bentuk kandidat dengan DIN terkecil ( ). Hapus dan semua bentuk yang bersinggungan.$\arg \min_{x} DIN(x)$
• Lanjutkan sampai tidak ada lagi kandidat yang tersisa.

Misalnya, perhatikan gambar berikut dari halaman Wikipedia:

Disk hijau memotong 5 disk lainnya, tetapi DIN-nya 3 (disk merah 3 saling lepas). Disk merah paling atas dan paling bawah memotong 2 disk lainnya, tetapi mereka sendiri berpotongan, sehingga DINnya adalah 1. Disk kuning memiliki DIN 2. Algoritma serakah dengan demikian memilih disk merah paling atas atau paling bawah.

Jika DIN minimum dapat dibatasi oleh konstanta, maka algoritma serakah adalah perkiraan faktor-konstan polinomial.

Sebagai contoh, jika semua bentuk kandidat adalah disk unit, Marathe et al (1995) menunjukkan bahwa disk dengan DIN paling banyak 3 selalu ada: disk paling kiri (disk dengan koordinat x terkecil) berpotongan di paling banyak 3 disk terpisah. . Oleh karena itu algoritma serakah menghasilkan perkiraan-3 karena memperoleh 1 disk untuk setiap (paling banyak) 3 disk dalam solusi optimal.

Demikian pula, jika semua bentuk kandidat adalah disk dengan ukuran sewenang-wenang, algoritma serakah menghasilkan perkiraan-5, karena disk terkecil memotong paling banyak 5 disk terpisah, yaitu DIN minimum paling banyak 5.

Sejauh ini bagus, tetapi Apakah faktor 3 dan 5 ini ketat? Saya tidak yakin.

Perhatikan gambar di atas. Memilih disk paling kiri (hijau) akan menemukan set ukuran terpisah 1, yang memang merupakan perkiraan 3 hingga set maksimum maksimum ukuran 3 (merah), tetapi, algoritma serakah tidak akan memilih disk hijau - ia akan memilih disk merah atas / bawah, yang DIN-nya adalah 1. Dalam hal ini algoritma serakah akan menemukan solusi optimal.

Saya tidak dapat menemukan contoh tandingan untuk umum , di mana algoritma serakah menemukan set disjoint dengan unit disk sedangkan set disjoint maksimum memiliki . Sebenarnya, saya bahkan tidak bisa membuat counter-contoh umum di mana DIN minimum memang 3. Yang terbaik yang bisa saya dapatkan adalah sebagai berikut, di mana setiap unit disk berpotongan paling banyak 2 disk terpisah lainnya (yaitu DIN minimum adalah 2). Tetapi bahkan di sini, algoritma serakah menemukan solusi optimal daripada perkiraan 2:n 3 $n$$n$$3n$

Pertanyaan saya adalah:

• Apa DIN min minimum sebenarnya dalam koleksi unit-disk? Disk berukuran sewenang-wenang?
• Apa faktor perkiraan sebenarnya dari algoritma serakah untuk koleksi unit-disk? Untuk disk berukuran sembarang? (faktor ini paling besar sebesar DIN min maks, tetapi mungkin lebih kecil).

UPDATE: Untuk setiap k-tuple bentuk, , tentukan = jumlah terbesar dari bentuk disjoint yang berpotongan dengan gabungannya . Tentukan sebagai DIN minimum untuk semua k-tupel bentuk terpisah. D I N ( x 1 , . . . , X k ) x 1 ∪ . . . ∪ x k m i n D I N $x_1,...,x_k$$DIN(x_1,...,x_k)$$x_1\cup...\cup x_k$$minDIN_k$

Misalnya, dalam jawaban Yury di bawah, , karena setiap lingkaran memotong 3 lingkaran lainnya. , karena dimungkinkan untuk memilih 2 lingkaran terpisah, satu dari lingkaran luar dan satu dari lingkaran dalam, yang bersama-sama hanya memotong 4 lingkaran lainnya. Untuk setiap , .$minDIN_1=3$$minDIN_2=4$$k$$minDIN_k\leq k+2$

Saya BERPIKIR bahwa rasio pendekatan algoritma serakah dapat dibatasi oleh , karena, untuk setiap bentuk dalam solusi optimal, kami memiliki setidaknya bentuk dalam output algoritma. Apakah ini benar?$\frac{minDIN_k}{k}$$minDIN_k$$k$

EDIT: Saya sekarang sedang membaca buku yang bagus Masalah penelitian dalam geometri diskrit . Meskipun saya belum menemukan masalah yang pasti ini, saya menemukan masalah yang sepertinya terkait. Di bagian "2.5 Paket Tipis dengan Banyak Tetangga", ada contoh paket lingkaran di mana setiap lingkaran menyentuh 5 lingkaran lainnya. Saya ingin tahu apakah pengepakan seperti itu dapat menghasilkan konfigurasi lingkaran dengan DIN = 5.

Berapa DIN minimum maksimum aktual dalam koleksi unit-disk?

Itu adalah 3.