Título: | SOLVING THE ONLINE PACKING IP UNDER SOME ADVERSARIAL INPUTS | ||||||||||||
Autor: |
DAVID BEYDA |
||||||||||||
Colaborador(es): |
MARCO SERPA MOLINARO - Orientador |
||||||||||||
Catalogação: | 23/JAN/2023 | Língua(s): | ENGLISH - UNITED STATES |
||||||||||
Tipo: | TEXT | Subtipo: | THESIS | ||||||||||
Notas: |
[pt] Todos os dados constantes dos documentos são de inteira responsabilidade de seus autores. Os dados utilizados nas descrições dos documentos estão em conformidade com os sistemas da administração da PUC-Rio. [en] All data contained in the documents are the sole responsibility of the authors. The data used in the descriptions of the documents are in conformity with the systems of the administration of PUC-Rio. |
||||||||||||
Referência(s): |
[pt] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=61783&idi=1 [en] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=61783&idi=2 |
||||||||||||
DOI: | https://doi.org/10.17771/PUCRio.acad.61783 | ||||||||||||
Resumo: | |||||||||||||
We study online packing integer programs, where the columns arrive one
by one. Since optimal algorithms were found for the RANDOMORDER model –
where columns arrive in random order – much focus of the area has been on less
optimistic models. One of those models is the MIXED model, where some columns
are adversarially ordered, while others come in random-order. Very few results are
known for packing IPs in the MIXED model, which is the object of our study.
We consider online IPs with d occupation dimensions (d packing constraints),
each one with capacity (or right-hand side) B. We also assume all items rewards
and occupations to be less or equal to 1. Our goal is to design an algorithm
where the presence of adversarial columns has a limited effect on the algorithm s
competitiveness relative to the random-order columns. Thus, we use OPTStoch – the
offline optimal solution considering only the random-order part of the input – as a
benchmark.We present an algorithm that, relative to OPTStoch, is (1−5 lambda− OBig O of epsilon)-competitive with high probability, where lambda is the fraction of adversarial columns.
In order to achieve such a guarantee, we make use of a primal-dual algorithm
where the decision variables are set by evaluating each item s reward and occupation
according to the dual variables of the IP, like other algorithms for the RANDOMORDER
model do. However, we can t hope to estimate those dual variables by
solving a scaled version of problem, because they could easily be manipulated by
an adversary in the MIXED model. Our solution was to use online learning techniques
to learn all aspects of the dual variables in an online fashion, as the problem
progresses.
|
|||||||||||||
|