Adakah algoritma cepat untuk masalah biaya umpan balik busur minimum?

Dalam grafik yang diarahkan, $G=(V,E)$ , , jika adalah DAG (grafik asiklik terarah), disebut set busur umpan balik. $F\subset E$ $G\setminus F$ $F$

Jika setiap sisi dikaitkan dengan bobot , masalah set busur umpan balik biaya minimum adalah untuk menemukan sehingga minimum. $w$ $F$ $W(F)$

Telah diketahui bahwa masalah set busur umpan balik minimum adalah NP-hard, dan demikian juga masalah set busur umpan balik biaya minimum. Saya ingin tahu apakah ada yang tahu algoritma perkiraan yang berkinerja baik, dan sifat-sifat fungsi berat yang dapat menghasilkan pemecah cepat.

ds.data-structures graph-theory np-hardness approximation-algorithms miao
sumber

Saya kira Anda mengetahui Even, Naor, Schieber, Sudan (1998): "Mendekati Set Umpan Balik Minimum dan Multicuts dalam Grafik Langsung " - dx.doi.org/10.1007/PL00009191 ?

Jukka Suomela

Ada beberapa penemuan independen dari pendekatan polylogarithmic untuk set busur umpan balik umum. Tergantung pada apa yang Anda cari, Anda mungkin ingin melihat semuanya. Lihat kertas Leighton dan Rao 1999; Seymour 1995; Bahkan et al. 2000; Bahkan et al. 1998 dikutip dalam cs.brown.edu/~ws/papers/fast_journal.pdf saya .

Warren Schudy

Hanya ingin memperjelas - apakah ini benar bahwa hanya masalah terarah NP-hard dan masalah untuk grafik tidak terarah dapat diselesaikan dalam waktu polinomial, lihat, misalnya diskusi stackoverflow "Bagaimana menemukan umpan balik diatur dalam grafik tidak terarah". Apakah ini benar bahwa masalahnya dapat diselesaikan dalam waktu polinomial untuk grafik yang tidak diarahkan?

TomR

@ TomR Tepi umpan balik berat minimum yang diatur dalam grafik tidak terarah memiliki pohon spanning berat maksimum sebagai pelengkapnya, yang dapat Anda temukan dalam polytime.

G. Bach

mungkin itu membantu: arxiv.org/pdf/1702.07612.pdf tepuk tangan dan semoga sukses

user44477

Jawaban:

Daniel Apon tertaut ke versi konferensi makalah saya. Saya menyarankan versi draft jurnal: http://www.cs.brown.edu/people/ws/papers/fast_journal.pdf .
Pada grafik turnamen, beberapa karya eksperimental menunjukkan bahwa pencarian lokal berjalan cukup baik. Lihat makalah ALENEX terbaru dari Anke van Zuylen dan Frans Schalekampf: http://www.siam.org/proceedings/alenex/2009/alx09_004_schalekampf.pdf .
Jika bobot memenuhi "kendala probabilitas" atau "ketidaksetaraan segitiga", ada algoritme pendekatan faktor konstan berdasarkan quicksort. Lihat Ailon, Charikar, dan makalah JACM terbaru Newman.
Bisakah Anda memberi tahu kami sedikit lebih banyak tentang contoh apa yang ada dalam pikiran Anda dan apakah Anda mencari sesuatu yang bekerja dengan baik dalam praktik atau secara teori?

Warren Schudy
sumber

Tautan Anda ke Zuylen dan Schalekampf sekarang adalah 404; informatik.uni-trier.de/~ley/pers/hd/s/Schalekamp:Frans

nodakai

Lihat makalah "Bagaimana Memberi Peringkat dengan Sedikit Kesalahan: Arc PTAS untuk Arc Umpan Balik Tertimbang di Turnamen" oleh Claire Kenyon-Mathieu dan Warren Schudy (STOC 2007, versi jurnal di halaman Schudy), yang memberikan skema perkiraan waktu Polinomial untuk kasus khusus di mana grafik yang diarahkan adalah turnamen.

DS
sumber

Kedua makalah ini sangat menarik. Selain itu, apakah ada pendekatan berbasis fungsi submodular di sekitar?

miao

Tolong beri tautan.

Emil

@Emil, salin / tempel nama kertas ke Google memberi Anda PDF pada klik pertama: PDF .

Daniel Apon

Saya hanya menyarankan cara untuk meningkatkan jawaban.

Emil