کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1141421 | 1489499 | 2015 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The hypergraph assignment problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: The hypergraph assignment problem The hypergraph assignment problem](/preview/png/1141421.png)
چکیده انگلیسی
The hypergraph assignment problem (HAP) generalizes the assignment problem from bipartite graphs to bipartite hypergraphs; it is motivated by applications in railway vehicle rotation planning. The HAP is NP-hard and APX-hard even for small hyperedge sizes and hypergraphs with a special partitioned structure. We show that an algorithmically tractable model providing a strong LP relaxation which implies all clique inequalities can be derived from a suitable extended formulation of polynomial size.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 15, February 2015, Pages 15-25
Journal: Discrete Optimization - Volume 15, February 2015, Pages 15-25
نویسندگان
Ralf Borndörfer, Olga Heismann,