University of Oulu
Oulu University Library
OuluCRIS
Laturi
Muuntaja

Similar Items

Cover Image

A. Elgabli and V. Aggarwal, "Deadline and Buffer Constrained Knapsack Problem," in IEEE Transactions on Circuits and Systems for Video Technology, vol. 29, no. 5, pp. 1564-1568, May 2019, doi: 10.1109/TCSVT.2019.2902759

Deadline and buffer constrained knapsack problem

Saved in:
Author: Elgabli, Anis1,2; Aggarwal, Vaneet3
Organizations: 1School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN 47907 USA
2Center of Wireless Communications, University of Oulu, 90014 Oulu, Finland
3School of Industrial Engineering, Purdue University, West Lafayette, IN 47907 USA
Format: article
Version: accepted version
Access: open
Online Access: PDF Full Text (PDF, 0.2 MB)
Persistent link: http://urn.fi/urn:nbn:fi-fe2020111390307
Language: English
Published: Institute of Electrical and Electronics Engineers, 2019
Publish Date: 2020-11-13
Description:

Abstract

In this paper, we formulate a problem that is a variant of the knapsack problem. Even though the problem is NP-hard in general, we consider a special case of the problem where the problem is in P. For this special case, the proposed algorithm is linear time complexity in the number of bins. The proposed framework is a generalization of the framework that has been used recently in the context of finding rate adaptation algorithms for video streaming.

see all
Series: IEEE transactions on circuits and systems for video technology
ISSN: 1051-8215
ISSN-E: 1558-2205
ISSN-L: 1051-8215
Volume: 29
Issue: 5
Pages: 1564 - 1568
DOI: 10.1109/TCSVT.2019.2902759
OADOI: https://oadoi.org/10.1109/TCSVT.2019.2902759
Type of Publication: A1 Journal article – refereed
Field of Science: 213 Electronic, automation and communications engineering, electronics
Subjects:
Knapsack problem
polynomial time algorithm
video streaming
Article
Copyright information: © 2019 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.