کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874259 | 686948 | 2015 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A generalization of extension complexity that captures P
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In this paper we propose a generalization of the extension complexity of a polyhedron Q. On the one hand it is general enough so that all problems in P can be formulated as linear programs with polynomial size extension complexity. On the other hand it still allows non-polynomial lower bounds to be proved for NP-hard problems independently of whether or not P=NP. The generalization, called H-free extension complexity, allows for a set of valid inequalities H to be excluded in computing the extension complexity of Q. We give results on the H-free extension complexity of hard matching problems (when H are the odd-set inequalities) and the traveling salesman problem (when H are the subtour elimination constraints).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 115, Issues 6â8, JuneâAugust 2015, Pages 588-593
Journal: Information Processing Letters - Volume 115, Issues 6â8, JuneâAugust 2015, Pages 588-593
نویسندگان
David Avis, Hans Raj Tiwary,