The design of competitive online algorithms via a primal–dual approach
N Buchbinder, JS Naor - Foundations and Trends® in …, 2009 - nowpublishers.com
The primal–dual method is a powerful algorithmic technique that has proved to be extremely
useful for a wide variety of problems in the area of approximation algorithms for NP-hard …
useful for a wide variety of problems in the area of approximation algorithms for NP-hard …
[HTML][HTML] A multi-agent coalition-based approach for order fulfilment in e-commerce
The rapid growth of e-commerce in the recent pandemic is driven by the wide adoption of
digitization, extensive use of smartphones, affordable internet services, and the convenience …
digitization, extensive use of smartphones, affordable internet services, and the convenience …
The power of clairvoyance for multi-level aggregation and set cover with delay
NM Le, S William Umboh, N Xie - Proceedings of the 2023 Annual ACM-SIAM …, 2023 - SIAM
Most online problems with delay require clairvoyance, the future delay of a request is known
upon its arrival, to achieve polylogarithmic competitiveness. An exception is Set Cover with …
upon its arrival, to achieve polylogarithmic competitiveness. An exception is Set Cover with …
General framework for metric optimization problems with delay or with deadlines
In this paper, we present a framework used to construct and analyze algorithms for online
optimization problems with deadlines or with delay over a metric space. Using this …
optimization problems with deadlines or with delay over a metric space. Using this …
Beyond tree embeddings–a deterministic framework for network design with deadlines or delay
We consider network design problems with deadline or delay. All previous results for these
models are based on randomized embedding of the graph into a tree (HST) and then …
models are based on randomized embedding of the graph into a tree (HST) and then …
Better approximation bounds for the joint replenishment problem
Abstract The Joint Replenishment Problem (JRP) deals with optimizing shipments of goods
from a supplier to retailers through a shared warehouse. Each shipment involves …
from a supplier to retailers through a shared warehouse. Each shipment involves …
A primal-dual online deterministic algorithm for matching with delays
M Bienkowski, A Kraska, HH Liu, P Schmidt - International Workshop on …, 2018 - Springer
Abstract In the Min-cost Perfect Matching with Delays (MPMD) problem, 2 m requests arrive
over time at points of a metric space. An online algorithm has to connect these requests in …
over time at points of a metric space. An online algorithm has to connect these requests in …
A match in time saves nine: Deterministic online matching with delays
M Bienkowski, A Kraska, P Schmidt - International Workshop on …, 2017 - Springer
We consider the problem of online Min-cost Perfect Matching with Delays (MPMD)
introduced by Emek et al.(STOC 2016). In this problem, an even number of requests appear …
introduced by Emek et al.(STOC 2016). In this problem, an even number of requests appear …
Online algorithms for multi-level aggregation
In the Multi-Level Aggregation Problem (MLAP), requests arrive at the nodes of an edge-
weighted tree T, and have to be served eventually. A service is defined as a subtree X of T …
weighted tree T, and have to be served eventually. A service is defined as a subtree X of T …
Nearly-tight lower bounds for set cover and network design with deadlines/delay
N Touitou - 32nd International Symposium on Algorithms and …, 2021 - drops.dagstuhl.de
In network design problems with deadlines/delay, an algorithm must make transmissions
over time to satisfy connectivity requests on a graph. To satisfy a request, a transmission …
over time to satisfy connectivity requests on a graph. To satisfy a request, a transmission …