Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Linear Discrepancy of Basic Totally Unimodular Matrices. | Linear Discrepancy of Basic Totally Unimodular Matrices Benjamin Doerr Mathematisches Seminar II Christian-Albrechts-Universitat zu Kiel Ludewig-Meyn-Str. 4 24098 Kiel Germany bed@numerik.uni-kiel.de Submitted April 6 2000 Accepted September 13 2000 AMS Subject Classification Primary 11K38 Abstract We show that the linear discrepancy of a basic totally unimodular matrix A 2 R txn is at most 1 nyy . This extends a result of Peng and Yan. AMS Subject Classification Primary 11K38. 1 Introduction and Results In PY00 Peng and Yan investigate the linear discrepancy of strongly unimodular 0 1 matrices. One part of their work is devoted to the case of basic strongly unimodular 0 1 matrices i. e. strongly unimodular 0 1 matrices which have at most two nonzeros in each row. The name basic is justified by a decomposition lemma for strongly unimodular matrices due to Crama Loebl and Poljak CLP92 . A matrix A is called totally unimodular if the determinant of each square submatrix is 1 0 or 1. In particular A is a 1 0 1 matrix. A is strongly unimodular if it is totally unimodular and if this also holds for any matrix obtained by replacing a single non-zero supported by the graduate school Effiziente Algorithmen und Multiskalenmethoden Deutsche Forschungsgemeinschaft THE ELECTRONIC .JOURNAL OF COMBINATORICS 7 2000 R48 2 entry of A with 0. Note that for matrices having at most two non-zeros per row both notions coincide. The linear discrepancy of an m X n matrix A is defined by lindisc A max min jD o i e 0 i n IIA p - x IU The objective of this note is to show Theorem. Let A be a totally unimodular m X n matrix which has at most two non-zeros per row. Then lindisc A 1 - 4ĩ. Our motivation is two-fold Firstly we extend the result in PY00 to arbitrary totally unimodular matrices having at most two non-zeros per row. We thus expand the assumption to include matrices with entries of -1 0 and 1. This enlarges the class of matrices for which Spencer s conjecture lindisc A 1 1 herdisc A
