Deadline and Buffer Constrained Knapsack Problem

Anis Elgabli; Vaneet Aggarwal

doi:10.1109/TCSVT.2019.2902759

Deadline and Buffer Constrained Knapsack Problem

Anis Elgabli, Vaneet Aggarwal^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

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.

Original language	English
Article number	8657784
Pages (from-to)	1564-1568
Number of pages	5
Journal	IEEE Transactions on Circuits and Systems for Video Technology
Volume	29
Issue number	5
DOIs	https://doi.org/10.1109/TCSVT.2019.2902759
State	Published - May 2019
Externally published	Yes

Bibliographical note

Publisher Copyright:
© 2018 IEEE.

Keywords

Knapsack problem
polynomial time algorithm
video streaming

ASJC Scopus subject areas

Media Technology
Electrical and Electronic Engineering

Access to Document

10.1109/TCSVT.2019.2902759

Cite this

@article{80ddad8bb5a74d219dac45fd6367d0da,

title = "Deadline and Buffer Constrained Knapsack Problem",

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.",

keywords = "Knapsack problem, polynomial time algorithm, video streaming",

author = "Anis Elgabli and Vaneet Aggarwal",

note = "Publisher Copyright: {\textcopyright} 2018 IEEE.",

year = "2019",

month = may,

doi = "10.1109/TCSVT.2019.2902759",

language = "English",

volume = "29",

pages = "1564--1568",

journal = "IEEE Transactions on Circuits and Systems for Video Technology",

issn = "1051-8215",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "5",

}

TY - JOUR

T1 - Deadline and Buffer Constrained Knapsack Problem

AU - Elgabli, Anis

AU - Aggarwal, Vaneet

PY - 2019/5

Y1 - 2019/5

N2 - 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.

AB - 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.

KW - Knapsack problem

KW - polynomial time algorithm

KW - video streaming

UR - https://www.scopus.com/pages/publications/85062645175

U2 - 10.1109/TCSVT.2019.2902759

DO - 10.1109/TCSVT.2019.2902759

M3 - Article

AN - SCOPUS:85062645175

SN - 1051-8215

VL - 29

SP - 1564

EP - 1568

JO - IEEE Transactions on Circuits and Systems for Video Technology

JF - IEEE Transactions on Circuits and Systems for Video Technology

IS - 5

M1 - 8657784

ER -

Deadline and Buffer Constrained Knapsack Problem

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this