Online combinatorial assignment in independence systems

Simple item page
dc.catalogadorjca
dc.contributor.authorMarinkovic, Javier
dc.contributor.authorSoto, Jose A.
dc.contributor.authorVerdugo Silva, Victor Ignacio
dc.date.accessioned2025-06-16T16:52:23Z
dc.date.available2025-06-16T16:52:23Z
dc.date.issued2025
dc.description.abstractWe consider an online multi-weighted generalization of several classic online optimization problems called the online combinatorial assignment problem. We are given an independence system over a ground set of elements and agents that arrive online one by one. Upon arrival, each agent reveals a weight function over the elements of the ground set. If the independence system is given by the matchings of a hypergraph, we recover the combinatorial auction problem, where every node represents an item to be sold, and every edge represents a bundle of items. For combinatorial auctions, Kesselheim et al. showed upper bounds of O (log log (k)/log (k) and O (log log (n)/log (n) on the competitiveness of any online algorithm, even in the random order model, where k is the maximum bundle size and n is the number of items. We provide an exponential improvement by giving upper bounds of O (log (k)/k, and O (log (n) for the prophet IID setting. Furthermore, using linear programming, we provide new and improved guarantees for the k-bounded online combinatorial auction problem (i.e., bundles of size at most k). We show a -competitive algorithm in the prophet IID model, a -competitive algorithm in the prophet-secretary model using a single sample per agent, and a -competitive algorithm in the secretary model. Our algorithms run in polynomial time and work in more general independence systems where the offline combinatorial assignment problem admits the existence of a polynomial-time randomized algorithm that we call certificate sampler. These systems include some classes of matroids, matroid intersections, and matchoids.
dc.fuente.origenWOS
dc.identifier.doi10.1007/s10107-025-02213-4
dc.identifier.eissn1436-4646
dc.identifier.issn0025-5610
dc.identifier.urihttps://doi.org/10.1007/s10107-025-02213-4
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/104670
dc.identifier.wosidWOS:001443852700001
dc.information.autorucInstituto de Ingeniería Matemática y Computacional; Verdugo Silva, Victor Ignacio; S/I; 1352043
dc.language.isoen
dc.nota.accesocontenido parcial
dc.pagina.final308
dc.pagina.inicio294
dc.revistaInteger Programming and Combinatorial Optimization
dc.rightsacceso restringido
dc.subjectOnline algorithms
dc.subjectLinear programming
dc.subjectCombinatorial auctions
dc.subject.ddc620
dc.subject.ods09 Industry, innovation and infrastructure
dc.subject.odspa09 Industria, innovación e infraestructura
dc.titleOnline combinatorial assignment in independence systems
dc.typecomunicación de congreso
sipa.codpersvinculados1352043
sipa.trazabilidadWOS;2025-03-29
Files
Collections
Artículos de conferencia