Record Detail
Advanced SearchText
On the adaptivity gap in two-stage robust linear optimization under uncertain packing constraints
In this paper, we study the performance of static solutions in two-stage adjustable robust packing linear optimization problem with uncertain constraint coefficients. Such problems arise in many important applications such as revenue management and resource allocation problems where demand requests have uncer-tain resource requirements. The goal is to find a two-stage solution that maximizes the worst case objective value over all possible realizations of the second-stage con-straints from a given uncertainty set. We consider the case where the uncertainty set is column-wise and constraint-wise (any constraint describing the set involve entries of only a single column or a single row). This is a fairly general class of uncer-tainty sets to model constraint coefficient uncertainty. We show that the two-stage adjustable robust problem is Ω(log
n)-hard to approximate. On the positive side, we show that a static solution is an O log n · min(log Γ, log(m + n)) -approximation for the two-stage adjustable robust problem where m and n denote the numbers of rows and columns of the constraint matrix and Γ is the maximum possible ratio of upper bounds of the uncertain constraint coefficients. Therefore, for constant Γ , surprisingly the performance bound for static solutions and therefore, the adaptivity gap matches the hardness of approximation for the adjustable problems. Furthermore, in general the static solution provides nearly the best efficient approximation for the two-stage adjustable robust problem.
File Attachment
Availability
EB00000003717K | Available |
Detail Information
Series Title |
-
|
---|---|
Call Number |
-
|
Publisher | : ., |
Collation |
-
|
Language | |
ISBN/ISSN |
-
|
Classification |
NONE
|
Content Type |
E-Jurnal
|
Media Type |
-
|
---|---|
Carrier Type |
-
|
Edition |
-
|
Subject(s) | |
Specific Detail Info |
-
|
Statement of Responsibility |
Pranjal Awasthi, Vineet Goyal, Brian Y.Lu
|
Other version/related
No other version available
OPAC
RECORD DETAIL
Back To Previous
Hari Lahir Pancasila: Ajang Mengenalkan Keragaman Suku Bangsa Budaya Indonesia
Universitas Jember menggelar Upacara Bendera Peringatan Hari Lahir Pancasila 1 Juni 2024. Upacara kali ini memiliki konsep yang berbeda dari tahun sebelumnya. Jika pada tahun sebelumnya hanya jajaran pimpinan yang menggunakan pakaian adat, namun tahun ini Mahasiwa, Dosen dan Tenaga...
BENGKEL SASTRA: MENGASAH BAKAT KEPENULISAN PUISI SANTRI JEMBER
Selasa (28/5), Santri se-Kabupaten Jember melakukan Library Tour di UPA Perpustakaan Universitas Jember. Kegiatan ini termasuk dalam serangkaian acara Bengkel Sastra yang dilaksanakan oleh Balai Bahasa Provinsi Jawa Timur. Kegiatan Bengkel Sastra dengan Tema “Penulisan Puisi Bagi Santri ...
EKSITSPACE: AJANG EKSPRESI SENI DAN LITERASI
Eksitspace kembali digelar pada Senin 27 Mei 2024. Eksitspace kali ini merupakan yang pertama kali digelar pada tahun 2024 yang juga dilaksanakan secara rutin tiap tahunnya. Eksitspace nantinya akan meramaikan lingkungan pepustakaan setiap bulannya dengan menampilkan pertunjukan ...