Vector assignment problems: A general framework

Leah Epstei, Tamir Tassa

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


We present a general framework for vector assignment problems, In such problems one aims at assigning n input vectors to m machines such that the value of a given target function is minimized. While previous approaches concentrated on simple target functions such as max-max, the general approach presented here enables us to design a polynomial time approximation scheme (PTAS) for a wide class of target functions. In particular, thanks to a novel technique of preprocessing the input vectors, we are able to deal with nonmonotone target functions. Such target functions arise in vector assignment problems in the context of video transmission and broadcasting.

שפה מקוריתאנגלית
עמודים (מ-עד)360-384
מספר עמודים25
כתב עתJournal of Algorithms
מספר גיליון2
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - ספט׳ 2003
פורסם באופן חיצוניכן

הערה ביבליוגרפית

Funding Information:
Research supported in part by the Israel Science Foundation (Grant 250/01).

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Vector assignment problems: A general framework'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי