Colección SciELO Chile

Departamento Gestión de Conocimiento, Monitoreo y Prospección
Consultas o comentarios: productividad@anid.cl
Búsqueda Publicación
Búsqueda por Tema Título, Abstract y Keywords



Prophet upper bounds for online matching and auctions
Indexado
WoS WOS:001468280500001
Scopus SCOPUS_ID:105001932017
DOI 10.1016/J.ORL.2025.107294
Año 2025
Tipo artículo de investigación

Citas Totales

Autores Afiliación Chile

Instituciones Chile

% Participación
Internacional

Autores
Afiliación Extranjera

Instituciones
Extranjeras


Abstract



In the online 2-bounded auction problem, we have a collection of items represented as nodes in a graph and bundles of size two represented by edges. Agents are presented sequentially, each with a random weight function over the bundles. The goal of the decision-maker is to find an allocation of bundles to agents of maximum weight so that every item is assigned at most once, i.e., the solution is a matching in the graph. When the agents are single-minded (i.e., put all the weight in a single bundle), we recover the maximum weight prophet matching problem under edge arrivals (a.k.a. prophet matching). In this work, we provide new and improved upper bounds on the competitiveness achievable by an algorithm for the general online 2-bounded auction and the (single-minded) prophet matching problems. For the adversarial arrival order of the agents, we show that no algorithm for the online 2-bounded auction problem achieves a competitiveness larger than 4/11, while no algorithm for prophet matching achieves a competitiveness larger than approximate to 0.4189. Using a continuous-time analysis, we also improve the known bounds for online 2-bounded auctions for random order arrivals to approximate to 0.5968 in the general case, a bound of approximate to 0.6867 in the IID model, and approximate to 0.6714 in prophet-secretary model.

Revista



Revista ISSN
Operations Research Letters 0167-6377

Métricas Externas



PlumX Altmetric Dimensions

Muestra métricas de impacto externas asociadas a la publicación. Para mayor detalle:

Disciplinas de Investigación



WOS
Operations Research & Management Science
Scopus
Industrial And Manufacturing Engineering
Software
Management Science And Operations Research
Applied Mathematics
SciELO
Sin Disciplinas

Muestra la distribución de disciplinas para esta publicación.

Publicaciones WoS (Ediciones: ISSHP, ISTP, AHCI, SSCI, SCI), Scopus, SciELO Chile.

Colaboración Institucional



Muestra la distribución de colaboración, tanto nacional como extranjera, generada en esta publicación.


Autores - Afiliación



Ord. Autor Género Institución - País
1 Soto, Jose A. - Universidad de Chile - Chile
2 Verdugo, Victor - Pontificia Universidad Católica de Chile - Chile

Muestra la afiliación y género (detectado) para los co-autores de la publicación.

Financiamiento



Fuente
FONDECYT
Anillo
Fondo Nacional de Desarrollo Científico y Tecnológico
CMM

Muestra la fuente de financiamiento declarada en la publicación.

Agradecimientos



Agradecimiento
ANID-Chile partially supported this research through grants CMM FB210005, FONDECYT 1231669, FONDECYT 1241846, and ANILLO ACT210005.
ANID-Chile partially supported this research through grants CMM FB210005, FONDECYT 1231669, FONDECYT 1241846, and ANILLO ACT210005.

Muestra la fuente de financiamiento declarada en la publicación.