All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 2 Next

Displaying 21 – 40 of 63

Showing per page

A note on the hardness results for the labeled perfect matching problems in bipartite graphs

Jérôme Monnot (2008)

RAIRO - Operations Research

In this note, we strengthen the inapproximation bound of O(logn) for the labeled perfect matching problem established in J. Monnot, The Labeled perfect matching in bipartite graphs, Information Processing Letters96 (2005) 81–88, using a self improving operation in some hard instances. It is interesting to note that this self improving operation does not work for all instances. Moreover, based on this approach we deduce that the problem does not admit constant approximation algorithms for connected...

A note on tree realizations of matrices

Alain Hertz, Sacha Varone (2007)

RAIRO - Operations Research

It is well known that each tree metric M has a unique realization as a tree, and that this realization minimizes the total length of the edges among all other realizations of M. We extend this result to the class of symmetric matrices M with zero diagonal, positive entries, and such that mij + mkl ≤ max{mik + mjl, mil + mjk} for all distinct i,j,k,l.

Currently displaying 21 – 40 of 63