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

DOI10.1007/978-3-319-03578-9_9zbMATH Open1407.68560arXiv1304.7687OpenAlexW2022134907MaRDI QIDQ2868635FDOQ2868635

Authors: Guy Even, Moti Medina 

Publication date: 17 December 2013

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

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (1)

• 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)