Polimetroid - Polymatroid

Bu maqola uchun qo'shimcha iqtiboslar kerak tekshirish. Iltimos yordam bering ushbu maqolani yaxshilang tomonidan ishonchli manbalarga iqtiboslarni qo'shish. Resurs manbasi bo'lmagan material shubha ostiga olinishi va olib tashlanishi mumkin. Manbalarni toping: "Polymatroid"  – Yangiliklar  · gazetalar  · kitoblar  · olim  · JSTOR (2011 yil fevral) (Ushbu shablon xabarini qanday va qachon olib tashlashni bilib oling)

Matematikada a polimetroid a politop bilan bog'liq submodular funktsiya. Tushunchasi tomonidan kiritilgan Jek Edmonds 1970 yilda.^[1] Shuningdek, u multiset analogi matroid.

Ta'rif

Ruxsat bering ${ displaystyle E}$ cheklangan bo'ling o'rnatilgan va ${ displaystyle f: 2 ^ {E} rightarrow mathbb {R} _ {+}}$ kamaymaydigan submodular funktsiya, ya'ni har biri uchun ${ displaystyle A subseteq B subseteq E}$ bizda ... bor ${ displaystyle f (A) leq f (B)}$va har biri uchun ${ displaystyle A, B subseteq E}$ bizda ... bor ${ displaystyle f (A) + f (B) geq f (A cup B) + f (A cap B)})$. Biz belgilaymiz polimetroid bilan bog'liq ${ displaystyle f}$ quyidagilar bo'lish politop:

${ displaystyle P_ {f}: = left {{ textbf {x}} in mathbb {R} _ {+} ^ {E} ~ | ~ sum _ {e in U} { textbf {x}} (e) leq f (U), forall U subeteq E right }}$.

Biz yozuvlariga ruxsat berganimizda ${ displaystyle { textbf {x}}}$ manfiy bo'lish uchun biz ushbu politopni quyidagicha belgilaymiz ${ displaystyle EP_ {f}}$va unga bog'langan kengaytirilgan polimetroid deb nomlang ${ displaystyle f}$.^[2]

Ekvivalent ta'rif

Ruxsat bering ${ displaystyle E}$ cheklangan bo'ling o'rnatilgan va ${ displaystyle { textbf {u}}, { textbf {v}} in mathbb {R} ^ {E}}$. Biz qo'ng'iroq qilamiz modul ning ${ displaystyle { textbf {u}}}$ uning barcha yozuvlari yig'indisi bo'lishi va belgilanishi kerak ${ displaystyle { textbf {u}} leq { textbf {v}}}$ har doim ${ displaystyle v_ {i} -u_ {i} geq 0}$ har bir kishi uchun ${ displaystyle i in E}$ (e'tibor bering, bu buyurtma ga ${ displaystyle mathbb {R} _ {+} ^ {E}}$). A polimetroid erga o'rnatilgan ${ displaystyle E}$ bo'sh emas ixcham kichik to'plam ${ displaystyle P}$ yilda ${ displaystyle mathbb {R} _ {+} ^ {E}}$, mustaqil vektorlar to'plami, quyidagilar:

1. Agar bizda shunday bo'lsa ${ displaystyle { textbf {v}} in P}$, keyin ${ displaystyle { textbf {u}} in P}$ har bir kishi uchun ${ displaystyle { textbf {u}} leq { textbf {v}}}$:
2. Agar ${ displaystyle { textbf {u}}, { textbf {v}} P}$ bilan ${ displaystyle | { textbf {v}} |> | { textbf {u}} |}$, keyin vektor mavjud ${ displaystyle w P}$ shu kabi ${ displaystyle { textbf {u}} <{ textbf {w}} leq ( max {u_ {1}, v_ {1} }, dots, max {u_ {| E |} , v_ {| E |} })}$.

Ushbu ta'rif ilgari tavsiflanganga teng^[3], qayerda ${ displaystyle f}$ tomonidan belgilangan funktsiya ${ displaystyle f (A) = max left { sum _ {i in A} { textbf {v}} (i) ~ | ~ { textbf {v}} in P right } }$ har bir kishi uchun ${ displaystyle A subset E}$.

Matroidlar bilan bog'liqlik

Barchaga matroid ${ displaystyle M}$ erga o'rnatilgan ${ displaystyle E}$ biz to'plamni birlashtira olamiz ${ displaystyle P_ {M} = {{ textbf {w}} _ {F} ~ | ~ F in M ​​}}$, har bir kishi uchun qaerda ${ displaystyle i in E}$ bizda shunday

${ displaystyle { textbf {w}} _ {F} (i) = { begin {case} 1, & i in F; 0, & i not in F. end {case}}}$

Qavariq tanasini olib ${ displaystyle P_ {M}}$ ning ikkinchi funktsiyasi ma'nosida, ning funktsiyasiga bog'liq bo'lgan polimetroidni olamiz ${ displaystyle M}$.

Umumlashtirilgan permutahedraga munosabat

Chunki umumlashtirilgan permutahedra submodular funktsiyalardan tuzilishi mumkin va har bir umumlashtirilgan permutahedr submodular funktsiyaga ega, bizda umumiy permutahedra va polymatroidlar o'rtasida yozishmalar bo'lishi kerak. Darhaqiqat, har bir polimetroid - bu kelib chiqishi cho'qqiga ega bo'lish uchun tarjima qilingan umumlashtirilgan permutaedr. Ushbu natija shuni ko'rsatadiki, polimetroidlarning kombinatorial ma'lumotlari umumiy permutahedraga etkaziladi.

Xususiyatlari

${ displaystyle P_ {f}}$ faqat agar shunday bo'lsa, bo'sh bo'lmaydi ${ displaystyle f geq 0}$ va bu ${ displaystyle EP_ {f}}$ agar kerak bo'lsa, bo'sh bo'lmaydi ${ displaystyle f ( emptyset) geq 0}$.

Har qanday kengaytirilgan polimetroid berilgan ${ displaystyle EP}$ noyob submodular funktsiya mavjud ${ displaystyle f}$ shu kabi ${ displaystyle f ( emptyset) = 0}$ va ${ displaystyle EP_ {f} = EP}$.

Kontrapolymatroidlar

Uchun super modulli f shunga o'xshash tarzda belgilanishi mumkin kontrapolymatroid

${ displaystyle left {w in mathbb {R} _ {+} ^ {E}: forall S subseteq E, sum _ {e in S} w (e) geq f (S) o'ng }}$

Bu o'xshashlik bilan dominantni umumlashtiradi spanning to'plami politop matroidlar.

Diskret polimetroidlar

Qachonki biz faqat panjara nuqtalari bizning polimetroidlarimiz biz nima deyiladi, diskret polimetroidlar. Rasmiy ravishda aytganda, a ta'rifi diskret polymatroid xuddi polimetroidlarnikiga to'g'ri keladi, faqat vektorlar o'rniga yashash joylari bundan mustasno ${ displaystyle mathbb {R} _ {+} ^ {E}}$ ular yashaydilar ${ displaystyle mathbb {Z} _ {+} ^ {E}}$. Ushbu kombinatoriya ob'ekti ularning munosabatlari tufayli katta qiziqish uyg'otadi monomial ideallar.

Adabiyotlar

Izohlar

Qo'shimcha o'qish

• Li, Jon (2004), Kombinatorial optimallashtirish bo'yicha birinchi kurs, Kembrij universiteti matbuoti, ISBN  0-521-01012-8
• Fujishige, Saruto (2005), Submodular funktsiyalar va optimallashtirish, Elsevier, ISBN  0-444-52086-4
• Narayanan, H. (1997), Submodular funktsiyalar va elektr tarmoqlari, ISBN  0-444-82523-1