Deadline and Buffer Constrained Knapsack Problem

被引：3

作者：

Elgabli, Anis ^{[1
,2
]}

Aggarwal, Vaneet ^{[3
]}

机构：

[1] Purdue Univ, Sch Elect & Comp Engn, W Lafayette, IN 47907 USA

[2] Univ Oulu, Ctr Wireless Commun, Oulu 90014, Finland

[3] Purdue Univ, Sch Ind Engn, W Lafayette, IN 47907 USA

来源：

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY | 2019年 / 29卷 / 05期

关键词：

Knapsack problem; video streaming; polynomial time algorithm; OPTIMIZATION;

D O I：

10.1109/TCSVT.2019.2902759

中图分类号：

TM [电工技术]; TN [电子技术、通信技术];

学科分类号：

0808 ; 0809 ;

摘要：

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.

引用

页码：1564 / 1568

页数：5

共 16 条

[1]

Abraham A., 2000, IEEE International Conf on Advanced Computing and Communications, P45

[2]

[Anonymous], 2014, Integer and Combinatorial Optimization

[3]

Bennett KP, 2006, J MACH LEARN RES, V7, P1265

[4]

Elgabli A., 2018, FASTSCAN ROBUST LOW

[5]

Elgabli A., 2018, IEEE T MOBILE COMPUT

[6]

Elgabli A., 2018, IEEE T CIRCUITS SYST

[7] LBP: Robust Rate Adaptation Algorithm for SVC Video Streaming [J].

Elgabli, Anis ;

Aggarwal, Vaneet ;

Hao, Shuai ;

Qian, Feng ;

Sen, Subhabrata .

IEEE-ACM TRANSACTIONS ON NETWORKING, 2018, 26 (04) :1633-1645

[8] A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems [J].

Jarboui, B. ;

Damak, N. ;

Siarry, P. ;

Rebai, A. .

APPLIED MATHEMATICS AND COMPUTATION, 2008, 195 (01) :299-308

[9]

Jillani R., 2008, ENCY MULTIMEDIA, P775, DOI [10.1007/978-0-387-78414-4_63, DOI 10.1007/978-0-387-78414-4_63]

[10]

Kreuzberger C., 2015, Proceedings of the 6th ACM Multimedia Systems Conference, P213, DOI [DOI 10.1145/2713168.2713193, 10.1145/2713168.2713193]

← 1 2 →