UPA Perpustakaan Universitas Jember

On the adaptivity gap in two-stage robust linear optimization under uncertain packing constraints

AWASTHI, Pranjal - Personal Name
GOYAL, Vineet - Personal Name
LU, Brian Y. - Personal Name

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.

EB00000003717K Available

Detail Information

Series Title

Call Number

Publisher

: ,

Collation

Language

ISBN/ISSN

Classification

NONE

Detail Information

Content Type

E-Jurnal

Media Type

Carrier Type

Edition

Subject(s)

Robust optimization ·
Approximation algorithms ·
Hardness of approximation

Specific Detail Info

Statement of Responsibility

Pranjal Awasthi, Vineet Goyal, Brian Y.Lu

No other version available

UPA Perpustakaan

Merupakan Unit Pendukung Akademis (UPA) yang bersama-sama dengan unit lain melaksanakan Tri Dharma Perguruan Tinggi (PT) melalui menghimpun, memilih, mengolah, merawat serta melayankan sumber informasi kepada civitas akademika Universitas Jember khususnya dan masyarakat akademis pada umumnya.

VISI

UPA Perpustakaan Universitas Jember sebagai perpustakaan modern dengan layanan prima yang mampu menunjang visi Universitas Jember.

MISI

Menyelenggarakan pembinaan dan pengembangan ketersediaan bahan pustaka dan informasi ilmiah sesuai dengan kebutuhan pemustaka secara berkelanjutan

Meningkatkan kualitas dan sistem manajemen layanan perpustakaan secara professional dengan memanfaatkan teknologi informasi

Membina dan mengembangkan jaringan kerjasama dengan pusat-pusat informasi dan lembaga terkait dalam dan luar negeri

UPA Perpustakaan Universitas Jember

NPP. 3509212D1000001

On the adaptivity gap in two-stage robust linear optimization under uncertain packing constraints

AWASTHI, Pranjal - Personal NameGOYAL, Vineet - Personal NameLU, Brian Y. - Personal Name

Series Title

Call Number

Publisher

Collation

Language

ISBN/ISSN

Classification

Content Type

Media Type

Carrier Type

Edition

Subject(s)

Specific Detail Info

Statement of Responsibility

About Us

UPA Perpustakaan

Total Koleksi

Total Item

Total Member

Total Pustakawan

Total Terpinjam

Peminjaman Tahun 2025

Peminjaman 5 Tahun

Peminjaman Bulan May 2025

Total Pengunjung

Pengunjung Tahun 2025

Pengunjung 5 Tahun Terakhir

Pengunjung Bulan May 2025

New collection + Update

Ngawur Karena Benar

Sagra

The Alpha Girl's Guide. Menjadi Cewek Smart, Independen, dan Anti - Galau

The Gallant Womens From Java. Wanita - Wanita Perkasa Dari Jawa

Filsafat Bahasa

Sastra Perlawanan. Menggugat Seni - Budaya Kapitalis, Menegakkan Seni - Sastra Kerakyatan yang Humanis - Kritis

Aplikasi Android

Our Services

Help Desk and Service Support UPA Perpustakaan

Tautan Pintas :

Jam Layanan :

Senin - Kamis:

Jum'at:

Sabtu dan Minggu:

Alamat & Kontak Info :

Jalan Kalimantan No. 37 - Kampus Bumi Tegalboto Kotak POS 159 Jember, Jawa Timur, 68121, Indonesia

library@unej.ac.id

(+62) 331 333860

AWASTHI, Pranjal - Personal Name
GOYAL, Vineet - Personal Name
LU, Brian Y. - Personal Name