In this paper, we focus on some specific optimization problems from graph theory, those for which all feasible solutions have an equal size that depends on the instance size. Once having provided a formal definition of this class of problems, we try to extract some of its basic properties; most of these are deduced from the equivalence, under differential approximation, between two versions of a problem which only differ on a linear transformation of their objective functions. This is notably...
In this paper, we focus on some specific optimization problems from graph
theory, those for which all feasible solutions have an equal size
that depends on the instance size.
Once having provided a formal definition of this class of
problems, we try to extract some of its basic properties; most of
these are deduced from the equivalence, under differential
approximation, between two versions of a problem which only
differ on a linear transformation of their objective functions.
This is notably...
In this note, we strengthen the inapproximation bound of (log) for the labeled perfect matching problem established in J.
Monnot, The Labeled perfect matching in bipartite graphs,
(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 planar cubic bipartite...
Download Results (CSV)