Balanced matrices and the set covering polytope

Abstract

A (01)matrix is said to be balanced if it does not contain any sub matrix of odd order with exactly two ones in each raw and each column A wellknown necessary (but not sufficient) condition for a (01)matrix A to be balanced in that the polytope associated with the linear programming relaxation of the set covering problem associated with A has only integral vertices ln this paper we characterize a class of (01)matrices A for which the above condition is also sufficient for A to be balanced This provides at the same time a new class of facet defining inequalities for the general set covering polytope where the coefficients can be arbitrary elements in {0 1 p} the p being a specified positive integer Some applications to the Kicover problem and Kiperfect graphs are also discussed

يقال عن مصفوفة عناصرها (0، 1) أنها متوازنة إذا كانت لا تحتوي على مصفوفة جزئية ذات مرتبة فردية تحتوي بالضبط على العنصر (1) مرتين في كل سطر وكل عمود، كشرط ضروريولكنه غير كافكي تكون مصفوفة (A) ذات العناصر (0، 1) متوازنة ؛ أن يحتوي متعدد الوجوهوهو المرافق للبرنامج الخطي الناتج عن مشكلة التغطية المرافقة للمصفوفة (A) بعد إسقاط القيود العدديةعلى زوايا عددية فقط في هذا البحث نحدد صنفا من المصفوفات (A) ذات العناصر (0، 1) بحيث يكون الشرط المنصوص عليه أعلاه كذلك شرطا كافيا كي تكون (A) متوازنة، كما يعطي في الوقت نفسه صنفا جديدا من المتراجحات الضرورية لمتعدد الوجوه المرافق لمشكلة التغطية في صورتها العامة بحيث أن الأمثال في هذه المتراجحات يمكن أن تكون أيا من الأعداد الصحيحة الموجبة (0، 1، 2، ، p)حيث P رقم معطى موجب وقد نوقشت كذلك بعض التطبيقات لمشكلة التغطية Ki–حيث ki للمشكلة والرسوم