این سایت در حال حاضر پشتیبانی نمی شود و امکان دارد داده های نشریات بروز نباشند
Iranian Journal of Numerical Analysis and Optimization، جلد ۱۲، شماره ۱، صفحات ۱۶۳-۱۷۱
عنوان فارسی
چکیده فارسی مقاله
کلیدواژه‌های فارسی مقاله
عنوان انگلیسی Connected bin packing problem on traceable graphs
چکیده انگلیسی مقاله We consider a new extension of the bin packing problem in which a set of connectivity constraints should be satisfied. An undirected graph with a weight function on the nodes is given. The objective is to pack all the nodes in the minimum number of unit-capacity bins, such that the induced subgraph on the set of nodes packed in each bin is connected. After analyzing some structural properties of the problem, we present a linear time approximation algorithm for this problem when the underlying graph is traceable. We show that the approximation factor of this algorithm is 2 and this factor is tight. Finally, concerning the investigated structural properties, we extend the algorithm for more general graphs. This extended algorithm also has a tight approximation factor of 2.
کلیدواژه‌های انگلیسی مقاله Bin Packing Problem, Connectivity, Complexity theory, Approximation Algorithms
نویسندگان مقاله A. Nejoomi |
Department of Computer Science, Shahed University, Tehran, Iran.

A. Dolati |
Department of Computer Science, Shahed University, Tehran, Iran.

نشانی اینترنتی https://ijnao.um.ac.ir/article_40635_e5f368461d145a66208acf1635aeba83.pdf
فایل مقاله فایلی برای مقاله ذخیره نشده است
کد مقاله (doi)
زبان مقاله منتشر شده en
موضوعات مقاله منتشر شده
نوع مقاله منتشر شده
برگشت به: صفحه اول پایگاه   |   نسخه مرتبط   |   نشریه مرتبط   |   فهرست نشریات