A nonmonotone analysis with the primal-dual approach: online routing of virtual circuits with unknown durations

DOI10.1007/978-3-319-03578-9_9zbMATH1407.68560OpenAlexW2022134907MaRDI QIDQ2868635FDOQ2868635

Authors Guy Even, Moti Medina

Publication date 17 December 2013

Published in Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.7687

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Analysis of algorithms (68W40)

Abstract: We address the question of whether the primal-dual approach for the design and analysis of online algorithms can be applied to nonmonotone problems. We provide a positive answer by presenting a primal-dual analysis to the online algorithm of Awerbuch et al.[AAPW01] for routing virtual circuits with unknown durations.

Recommendations

• A nonmonotone analysis with the primal-dual approach: online routing of virtual circuits with unknown durations
• Online primal-dual for non-linear optimization with applications to speed scaling
• The Design of Competitive Online Algorithms via a Primal—Dual Approach
• Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue
• On-line routing of virtual circuits with applications to load balancing and machine scheduling

Cites work

• Competitive routing of virtual circuits with unknown duration
• Frequency capping in online advertising (extended abstract)
• On-Line Load Balancing of Temporary Tasks
• On-line routing of virtual circuits with applications to load balancing and machine scheduling
• The Design of Competitive Online Algorithms via a Primal—Dual Approach

Cited in

(2)

• A nonmonotone analysis with the primal-dual approach: online routing of virtual circuits with unknown durations
• Online admission control and embedding of service chains

This page was built for publication: A nonmonotone analysis with the primal-dual approach: online routing of virtual circuits with unknown durations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2868635)