Menghasilkan suatu titik dalam sebuah polytope rasional diberi sebuah titik dalam

8

Pertimbangkan polytope rasional yang didefinisikan dengan cara oracle pemisahan. Yaitu, dapat digambarkan secara implisit sebagai , tetapi karena adalah sangat besar, kami menggunakan oracle, yang diberi titik , baik kata atau kembali setengah-ruang sehingga .P P = { x R k : A x b , A Z m × k , b Z m } m x R k x P x SPPP={xRk:Axb,AZm×k,bZm}mxRkxPxS

Tujuan saya adalah menemukan titik di atau menentukan bahwa kosong. Aku bertujuan untuk waktu yang berjalan polinomial dalam ukuran representasi dari dan , di mana adalah nilai absolut terbesar di . Artinya, algoritma harus membuat hanya banyak panggilan polinomial ke oracle pemisahan.P U k U APPUkUA

Secara umum, mungkin terkandung dalam bidang hyper-dimensi yang lebih rendah dan dengan demikian itu bermasalah untuk menggunakan metode ellipsoid. Jadi, seperti dalam trik Khachiyan, saya alter (dan oracle pemisahan) untuk menggunakan , di mana adalah sesuatu seperti . Secara intuitif, setengah spasi yang mendefinisikan adalah sama dengan yang mendefinisikan hanya bahwa mereka diterjemahkan oleh . Polytope memiliki sifat berikut: kosong jika kosong, dan jika tidak kosong,P P ϵ ϵ 1 / U P ϵ P ϵ P ϵ P ϵ P P P ϵPPPϵϵ1/UPϵPϵPϵPϵPPPϵ adalah dimensi penuh.

Pertanyaan saya adalah sebagai berikut: Asumsikan algoritma menemukan titik . Apakah mungkin untuk menghasilkan titik dalam menggunakan ? P ppPϵPp

Orang
sumber

Jawaban:

8

Dari sembarang pilihan polytope dalam , , dan titik dalam adalah mungkin untuk menemukan polytope dalam , bersama-sama dengan penyisipan ke , sedemikian sehingga berada dalam jarak Hausdorff dari (gambar yang disematkan) dan semacamnya bahwa (gambar yang disematkan) milik . Untuk melakukan ini, cukup buat sisiR k ε q R k P R k + 1 R k R k + 1 P ε P q P ε P R k ε R k + 1 R k PPRkϵqRkP^Rk+1RkRk+1P^ϵPqP^ϵP^hampir sejajar dengan gambar tertanam , sehingga menerjemahkannya dengan di menyebabkan persimpangan dengan untuk menjauh dari dengan jarak yang jauh lebih besar.RkϵRk+1RkP^

Karena sewenang-wenang, pengetahuan tentang tidak ada gunanya menemukan titik di atau dekat ; semua yang bisa Anda lakukan dengannya bisa Anda lakukan tanpanya. Tapi, karena dan begitu dekat, menemukan titik dekat setara dengan menemukan titik dekat . Oleh karena itu, pengetahuan tentang (titik di ) tidak ada gunanya dalam menemukan titik dekat .q P P P P P q P ε PqqPP^PPP^qP^ϵP^

David Eppstein
sumber
Terima kasih! Saya menambahkan asumsi bahwa polytope itu rasional, jadi (semoga) sekarang, ada harapan untuk menemukan titik di P.
Guy
Pembatasan itu tidak membantu; mudah untuk membuat P rasional dalam konstruksi Daud. P^
Jeffε
Saya kira si penanya benar-benar bertanya bagaimana menemukan titik ketika P tidak berdimensi penuh. pPP
Chandra Chekuri
2

Jika tujuan Anda adalah menemukan titik di atau menentukan bahwa P kosong, mengapa Anda tidak melakukan yang berikut.PP

Biarkan menjadi seperangkat ruang setengah, awalnya kosong.H

Biarkan menjadi titik, awalnya sama dengan 0 k .x0k

  1. Berikan pada oracle.x

  2. Jika oracle berkata , Anda sudah selesai.xP

  3. Kalau tidak, biarkan menjadi ruang setengah yang dilanggar yang dikembalikan oleh oracle. Biarkan y menjadi proyeksi ortogonal x di S . SyxS

    • Jika ada setidaknya satu sehingga y T , maka Anda telah melakukan: P kosong.THyTP
    • Kalau tidak, atur , dan atur x : = y . H:=H{S}x:=y
  4. Kembali ke 1.

Giorgio Camerani
sumber
Terima kasih atas tanggapannya. Saya pikir itu akan bekerja, tapi, kecuali jika saya melewatkan sesuatu, waktu berjalan akan porportional untuk , jumlah setengah-ruang yang mendefinisikan P . Aku berharap untuk waktu yang berjalan yang jumlahnya banyak di k dan representasi U , yang merupakan nilai terbesar mutlak dalam A . Artinya, hanya banyak polinomial panggilan ke oracle. mPkUA
Pria
Sama sama! Apakah Anda yakin persyaratan seperti itu tentang waktu berjalan terbukti dengan membaca pertanyaan?
Giorgio Camerani
1
Kamu benar. Saya akan menambahkannya.
Pria