Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Biobjective Optimization Problems on Matroids with Binary Costs   Like most multiobjective combinatorial optimization problems, biobjective
optimization problems on matroids are in general intractable and their
corresponding decision problems are in general NP-hard. In this paper, we
consider biobjective optimization problems on matroids where one of the
objective functions is restricted to binary cost coefficients. We show that in
this case the problem has a connected efficient set with respect to a natural
definition of a neighborhood structure and hence, can be solved efficiently
using a neighborhood search approach. This is, to the best of our knowledge,
the first non-trivial problem on matroids where connectedness of the efficient
set can be established.
  The theoretical results are validated by numerical experiments with
biobjective minimum spanning tree problems (graphic matroids) and with
biobjective knapsack problems with a cardinality constraint (uniform matroids).
In the context of the minimum spanning tree problem, coloring all edges with
cost 0 green and all edges with cost 1 red leads to an equivalent problem where
we want to simultaneously minimize one general objective and the number of red
edges (which defines the second objective) in a Pareto sense.

23
The categories of this paper are: solv-int
32
The categories of this paper are: atom-ph
27
The categories of this paper are: comp-gas
12
The categories of this paper are: nucl-th
0
The categories of this paper are: hep-ph
8
The categories of this paper are: hep-ex
11
The categories of this paper are: hep-lat
31
The categories of this paper are: ao-sci
4
The categories of this paper are: cond-mat
29
The categories of this paper are: funct-an
28
The categories of this paper are: alg-geom
24
The categories of this paper are: dg-ga
9
The categories of this paper are: nlin
22
The categories of this paper are: chao-dyn
35
The categories of this paper are: mtrl-th
25
The categories of this paper are: patt-sol