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
مستوى الصوت48
رقم الإصدار2
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - سبتمبر 2003
منشور خارجيًانعم

ملاحظة ببليوغرافية

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


أدرس بدقة موضوعات البحث “Vector assignment problems: A general framework'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا