Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Robust Assignments via Ear Decompositions and Randomized Rounding   Many real-life planning problems require making a priori decisions before all
parameters of the problem have been revealed. An important special case of such
problem arises in scheduling problems, where a set of tasks needs to be
assigned to the available set of machines or personnel (resources), in a way
that all tasks have assigned resources, and no two tasks share the same
resource. In its nominal form, the resulting computational problem becomes the
\emph{assignment problem} on general bipartite graphs.
  This paper deals with a robust variant of the assignment problem modeling
situations where certain edges in the corresponding graph are \emph{vulnerable}
and may become unavailable after a solution has been chosen. The goal is to
choose a minimum-cost collection of edges such that if any vulnerable edge
becomes unavailable, the remaining part of the solution contains an assignment
of all tasks.
  We present approximation results and hardness proofs for this type of
problems, and establish several connections to well-known concepts from
matching theory, robust optimization and LP-based techniques.

6
The categories of this paper are: astro-ph
20
The categories of this paper are: acc-phys
28
The categories of this paper are: alg-geom
33
The categories of this paper are: plasm-ph
26
The categories of this paper are: bayes-an
23
The categories of this paper are: solv-int
34
The categories of this paper are: chem-ph
14
The categories of this paper are: math-ph
0
The categories of this paper are: hep-ph
11
The categories of this paper are: hep-lat
4
The categories of this paper are: cond-mat
31
The categories of this paper are: ao-sci
18
The categories of this paper are: econ
22
The categories of this paper are: chao-dyn
30
The categories of this paper are: q-alg
5
The categories of this paper are: gr-qc