@inproceedings{Beckenbach, author = {Beckenbach, Isabel}, title = {A Hypergraph Network Simplex Algorithm}, series = {Operations Research Proceedings 2017}, volume = {Operations Research Proceedings 2017}, booktitle = {Operations Research Proceedings 2017}, editor = {Kliewer, Natalia and Ehmke, Jan Fabian and Bornd{\"o}rfer, Ralf}, publisher = {Springer}, address = {Cham}, pages = {309 -- 316}, abstract = {We describe a network simplex algorithm for the minimum cost flow problem on graph-based hypergraphs which are directed hypergraphs of a particular form occurring in railway rotation planning. The algorithm is based on work of Cambini, Gallo, and Scutell{\`a} who developed a hypergraphic generalization of the network simplex algorithm. Their main theoretical result is the characterization of basis matrices. We give a similar characterization for graph-based hypergraphs and show that some operations of the simplex algorithm can be done combinatorially by exploiting the underlying digraph structure.}, language = {en} } @inproceedings{BeckenbachBorndoerfer, author = {Beckenbach, Isabel and Bornd{\"o}rfer, Ralf}, title = {An Approximation Result for Matchings in Partitioned Hypergraphs}, series = {Operations Research Proceedings 2014}, booktitle = {Operations Research Proceedings 2014}, publisher = {Springer International Publishing}, doi = {10.1007/978-3-319-28697-6_5}, pages = {31 -- 36}, abstract = {We investigate the matching and perfect matching polytopes of hypergraphs having a special structure, which we call partitioned hypergraphs. We show that the integrality gap of the standard LP-relaxation is at most \$2\sqrt{d}\$ for partitioned hypergraphs with parts of size \$\leq d\$. Furthermore, we show that this bound cannot be improved to \$\mathcal{O}(d^{0.5-\epsilon})\$.}, language = {en} }