A simple proof of the generalized farkas lemma for oriented matroids

L. Balogh, T. Illes, F. Erbilen

Research output: Contribution to journalArticle

Abstract

In this note we consider the feasibility problem of oriented matroids. An alternative
theorem, which is a generalization of Farkas’ famous result, is stated and proved. Our proof is constructive and new. In the proof of the generalized Farkas lemma, the finiteness of a criss-cross type algorithm is used. The algorithm’s pivot rule, for criss-cross type methods, first was used by S. Zhang for linear programming problems.
LanguageEnglish
Pages423-431
Number of pages9
JournalPure Mathematics and Applications
Volume13
Issue number4
Publication statusPublished - 1 Dec 2002

Fingerprint

Farkas Lemma
Oriented Matroid
Pivot
Finiteness
Linear programming
Generalization

Keywords

  • matroids
  • oriented matroids
  • feasibility problem of oriented matroids
  • criss-cross type algorithm

Cite this

Balogh, L. ; Illes, T. ; Erbilen, F. / A simple proof of the generalized farkas lemma for oriented matroids. In: Pure Mathematics and Applications. 2002 ; Vol. 13, No. 4. pp. 423-431.
@article{cb179a5742724e51a39ff01fda7f86e7,
title = "A simple proof of the generalized farkas lemma for oriented matroids",
abstract = "In this note we consider the feasibility problem of oriented matroids. An alternativetheorem, which is a generalization of Farkas’ famous result, is stated and proved. Our proof is constructive and new. In the proof of the generalized Farkas lemma, the finiteness of a criss-cross type algorithm is used. The algorithm’s pivot rule, for criss-cross type methods, first was used by S. Zhang for linear programming problems.",
keywords = "matroids, oriented matroids, feasibility problem of oriented matroids, criss-cross type algorithm",
author = "L. Balogh and T. Illes and F. Erbilen",
year = "2002",
month = "12",
day = "1",
language = "English",
volume = "13",
pages = "423--431",
journal = "Pure Mathematics and Applications",
issn = "1218-4586",
number = "4",

}

Balogh, L, Illes, T & Erbilen, F 2002, 'A simple proof of the generalized farkas lemma for oriented matroids' Pure Mathematics and Applications, vol. 13, no. 4, pp. 423-431.

A simple proof of the generalized farkas lemma for oriented matroids. / Balogh, L.; Illes, T.; Erbilen, F.

In: Pure Mathematics and Applications, Vol. 13, No. 4, 01.12.2002, p. 423-431.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A simple proof of the generalized farkas lemma for oriented matroids

AU - Balogh, L.

AU - Illes, T.

AU - Erbilen, F.

PY - 2002/12/1

Y1 - 2002/12/1

N2 - In this note we consider the feasibility problem of oriented matroids. An alternativetheorem, which is a generalization of Farkas’ famous result, is stated and proved. Our proof is constructive and new. In the proof of the generalized Farkas lemma, the finiteness of a criss-cross type algorithm is used. The algorithm’s pivot rule, for criss-cross type methods, first was used by S. Zhang for linear programming problems.

AB - In this note we consider the feasibility problem of oriented matroids. An alternativetheorem, which is a generalization of Farkas’ famous result, is stated and proved. Our proof is constructive and new. In the proof of the generalized Farkas lemma, the finiteness of a criss-cross type algorithm is used. The algorithm’s pivot rule, for criss-cross type methods, first was used by S. Zhang for linear programming problems.

KW - matroids

KW - oriented matroids

KW - feasibility problem of oriented matroids

KW - criss-cross type algorithm

M3 - Article

VL - 13

SP - 423

EP - 431

JO - Pure Mathematics and Applications

T2 - Pure Mathematics and Applications

JF - Pure Mathematics and Applications

SN - 1218-4586

IS - 4

ER -