Packing Resizable Items with Application to Video Delivery over Wireless Networks

Autor:	Sivan Albagli-Kim, Hadas Shachnai, Leah Epstein, Tami Tamir
Rok vydání:	2013
Předmět:	Combinatorics Set (abstract data type) Cardinality Optimization problem business.industry Computer science Wireless network Interval (graph theory) Fraction (mathematics) Video delivery business Bin Computer network
Zdroj:	Algorithms for Sensor Systems ISBN: 9783642360916 ALGOSENSORS
DOI:	10.1007/978-3-642-36092-3_3
Popis:	Motivated by fundamental optimization problems in video delivery over wireless networks, we consider the following problem of packing resizable items (PRI). Given is a bin of capacity B > 0, and a set I of items. Each item j ∈ I is of size s j > 0. A packed item must stay in the bin for a fixed time interval. To accommodate more items in the bin, each item j can be compressed to a size p j ∈ [0,s j ) for at most a fraction q j ∈ [0,1) of the packing interval. The goal is to pack in the bin, for the given time interval, a subset of items of maximum cardinality. PRI is strongly NP-hard already for highly restricted instances.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::d037352370caf59054c46be965939c70 https://doi.org/10.1007/978-3-642-36092-3_3 Zobrazit plný text záznamu