On computation of performance bounds of optimal index assignment

Xiaolin Wu; Hans Mittelmann; Xiaohan Wang; Jia Wang

doi:10.1109/DCC.2010.24

On computation of performance bounds of optimal index assignment

Xiaolin Wu, Hans Mittelmann, Xiaohan Wang, Jia Wang

Mathematical and Statistical Sciences, School of (SoMSS)

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Scopus citations

Abstract

Channel-optimized index assignment of source codewords is arguably the simplest way of improving transmission error resilience, while keeping the source and/or channel codes intact. But optimal design of index assignment is an in-stance of quadratic assignment problem (QAP), one of the hardest optimization problems in the NP-complete class. In this paper we make a progress in the research of index assignment optimization. We apply some recent results of QAP research to compute the strongest lower bounds so far for channel distor-tion of BSC among all index assignments. The strength of the resulting lower bounds is validated by comparing them against the upper bounds produced by heuristic index assignment algorithms.

Original language	English (US)
Title of host publication	Proceedings - Data Compression Conference, DCC 2010
Pages	189-198
Number of pages	10
DOIs	https://doi.org/10.1109/DCC.2010.24
State	Published - 2010
Event	Data Compression Conference, DCC 2010 - Snowbird, UT, United States Duration: Mar 24 2010 → Mar 26 2010

Publication series

Name	Data Compression Conference Proceedings
ISSN (Print)	1068-0314

Other

Other	Data Compression Conference, DCC 2010
Country/Territory	United States
City	Snowbird, UT
Period	3/24/10 → 3/26/10

Keywords

Error resilience
Index assignment
Quadratic assignment
Quantization
Relaxation
Semidefinite programming

ASJC Scopus subject areas

Computer Networks and Communications

Access to Document

10.1109/DCC.2010.24

Cite this

@inproceedings{1b6035f34372441faf15f52c37c89d34,

title = "On computation of performance bounds of optimal index assignment",

abstract = "Channel-optimized index assignment of source codewords is arguably the simplest way of improving transmission error resilience, while keeping the source and/or channel codes intact. But optimal design of index assignment is an in-stance of quadratic assignment problem (QAP), one of the hardest optimization problems in the NP-complete class. In this paper we make a progress in the research of index assignment optimization. We apply some recent results of QAP research to compute the strongest lower bounds so far for channel distor-tion of BSC among all index assignments. The strength of the resulting lower bounds is validated by comparing them against the upper bounds produced by heuristic index assignment algorithms.",

keywords = "Error resilience, Index assignment, Quadratic assignment, Quantization, Relaxation, Semidefinite programming",

author = "Xiaolin Wu and Hans Mittelmann and Xiaohan Wang and Jia Wang",

year = "2010",

doi = "10.1109/DCC.2010.24",

language = "English (US)",

isbn = "9780769539942",

series = "Data Compression Conference Proceedings",

pages = "189--198",

booktitle = "Proceedings - Data Compression Conference, DCC 2010",

}

TY - GEN

T1 - On computation of performance bounds of optimal index assignment

AU - Wu, Xiaolin

AU - Mittelmann, Hans

AU - Wang, Xiaohan

AU - Wang, Jia

PY - 2010

Y1 - 2010

N2 - Channel-optimized index assignment of source codewords is arguably the simplest way of improving transmission error resilience, while keeping the source and/or channel codes intact. But optimal design of index assignment is an in-stance of quadratic assignment problem (QAP), one of the hardest optimization problems in the NP-complete class. In this paper we make a progress in the research of index assignment optimization. We apply some recent results of QAP research to compute the strongest lower bounds so far for channel distor-tion of BSC among all index assignments. The strength of the resulting lower bounds is validated by comparing them against the upper bounds produced by heuristic index assignment algorithms.

AB - Channel-optimized index assignment of source codewords is arguably the simplest way of improving transmission error resilience, while keeping the source and/or channel codes intact. But optimal design of index assignment is an in-stance of quadratic assignment problem (QAP), one of the hardest optimization problems in the NP-complete class. In this paper we make a progress in the research of index assignment optimization. We apply some recent results of QAP research to compute the strongest lower bounds so far for channel distor-tion of BSC among all index assignments. The strength of the resulting lower bounds is validated by comparing them against the upper bounds produced by heuristic index assignment algorithms.

KW - Error resilience

KW - Index assignment

KW - Quadratic assignment

KW - Quantization

KW - Relaxation

KW - Semidefinite programming

UR - http://www.scopus.com/inward/record.url?scp=77952699962&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77952699962&partnerID=8YFLogxK

U2 - 10.1109/DCC.2010.24

DO - 10.1109/DCC.2010.24

M3 - Conference contribution

AN - SCOPUS:77952699962

SN - 9780769539942

T3 - Data Compression Conference Proceedings

SP - 189

EP - 198

BT - Proceedings - Data Compression Conference, DCC 2010

T2 - Data Compression Conference, DCC 2010

Y2 - 24 March 2010 through 26 March 2010

ER -

On computation of performance bounds of optimal index assignment

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Cite this