A Constant Approximation Algorithm for Scheduling Packets on Line Networks

DOI10.4230/LIPICS.ESA.2016.40MaRDI QIDQ4606311zbMATH OpenOpenAlexFDO

Authors Guy Even, Moti Medina, Adi Rosén

Publication date 2 March 2018

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

zbMATH Keywords

linear programmingapproximation algorithmsadmission controlpacket schedulingrandomized rounding

Mathematics Subject Classification ID

Linear programming (90C05) Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Abstract: In this paper we improve the approximation ratio for the problem of scheduling packets on line networks with bounded buffers, where the aim is that of maximizing the throughput. Each node in the network has a local buffer of bounded size $B$, and each edge (or link) can transmit a limited number, $c$, of packets in every time unit. The input to the problem consists of a set of packet requests, each defined by a source node, a destination node, and a release time. We denote by $n$ the size of the network. A solution for this problem is a schedule that delivers (some of the) packets to their destinations without violating the capacity constraints of the network (buffers or edges). Our goal is to design an efficient algorithm that computes a schedule that maximizes the number of packets that arrive to their respective destinations. We give a randomized approximation algorithm with constant approximation ratio for the case where $B=Theta(c)$. This improves over the previously best result of $O(lo{g}^{\ast }n)$ (R"acke and Ros'en, Theory Comput. Syst., 49(4), 2011). Our improvement is based on a new combinatorial lemma that we prove, stating, roughly speaking, that if packets are allowed to stay put in buffers only a limited number of time steps, $2d$, where $d$ is the longest source-destination distance of any input packet, then the cardinality of the optimal solution is decreased by only a constant factor. This claim was not previously known in the directed integral (i.e., unsplittable, zero-one) case, and may find additional applications for routing and scheduling algorithms.

Recommendations

• Approximation algorithms for time-constrained scheduling on line networks
• An optimal online algorithm for packet scheduling with agreeable deadlines
• Approximate sorting of packet-scheduling in high-speed networks
• A \(\boldsymbol{\phi }\) -Competitive Algorithm for Scheduling Packets with Deadlines
• A -competitive algorithm for scheduling packets with deadlines
• Online packet scheduling with bounded delay and lookahead
• Online packet scheduling with bounded delay and lookahead
• Online scheduling of packets with agreeable deadlines
• A comprehensive study of an online packet scheduling algorithm

Cited in

(7)

• scientific article; zbMATH DE number 1559579 (Why is no real title available?)
• A universal randomized packet scheduling algorithm
• Approximation algorithms for time-constrained scheduling on line networks
• A constant-factor approximation algorithm for packet routing and balancing local vs. global criteria
• Universal stability in multi-hop radio networks
• Time-constrained scheduling of weighted packets on trees and meshes
• Online packet-routing in grids with bounded buffers

This page was built for publication: A Constant Approximation Algorithm for Scheduling Packets on Line Networks

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