Several of the natural combinatorial optimization problems are NP-complete,
which means that under certain reasonable assumption, it is not possible to solve
these problems exactly in polynomial time. Hence efficient algorithms that find
approximate solutions to these problems, are desired. These algorithms must come
with the guarantee that for all instances of the given problem, the cost of
the solution found is within a promised factor of the optimum cost.
We are looking at certain problems that arise when the AND constraints are
relaxed to OR constraints. For example in the matching problem, a solution must consist of
a subset of edges where for each edge in the solution the number of incident edges
at the two end-points are both bounded by 1. We relax this constraint from
"both end-points" to "at least one end-point" and the resulting problem is shown
to be NP-complete whereas the original matching problem has a polynomial time solution.
We study several variants of the resulting problem. In immediate future we hope to
find more such problems where replacing a conjunctive constraint with a
disjunctive constraint makes the problem interesting.

## Research Areas

paurora[AT]iiserb.ac.in

Several of the natural combinatorial optimization problems are NP-complete, which means that under certain reasonable assumption, it is not possible to solve these problems exactly in polynomial time. Hence efficient algorithms that find approximate solutions to these problems, are desired. These algorithms must come with the guarantee that for all instances of the given problem, the cost of the solution found is within a promised factor of the optimum cost. We are looking at certain problems that arise when the AND constraints are relaxed to OR constraints. For example in the matching problem, a solution must consist of a subset of edges where for each edge in the solution the number of incident edges at the two end-points are both bounded by 1. We relax this constraint from "both end-points" to "at least one end-point" and the resulting problem is shown to be NP-complete whereas the original matching problem has a polynomial time solution. We study several variants of the resulting problem. In immediate future we hope to find more such problems where replacing a conjunctive constraint with a disjunctive constraint makes the problem interesting.