# Do there exist “odd times” cover problems and what do we know about their approximability?

I am currently investigating a problem which can be formulated as a cover problem, in which real intervals have to be covered an odd number of times by integers.

My question is just, if anybody has heard of cover problems in which the items have to be covered an odd number of times. And if so, are there any results about the (in)approximability of such problems known.

• Is nonoverlapping hyperspheres a subset of this domain? Overlap by two hyperspheres would mean an even cover. – Chad Brewbaker Apr 11 '14 at 15:01
• – Marzio De Biasi Apr 11 '14 at 15:07
• ... 3) Algebraic Problems in Computational Complexity ... odd cover problem: cover $K_n$ using complete bipartite graphs, such that each edge is covered an odd number of times. (for infinitely many $n$ it is $\lceil n/2 \rceil$) – Marzio De Biasi Apr 11 '14 at 15:15
• ... 4) Cover with eulerian graphs: it is proved that every eulerian simple graph on n vertices can be covered by at most $\lfloor (n-1)/2 \rfloor$ circuits such that each edge is covered an odd number of times; and 5) on the "Number Theory side" see also the Erdos-Selfridge Conjecture – Marzio De Biasi Apr 11 '14 at 15:26
• Writing down the complete problem will increase the chance of obtaining answers. Thanks – Vivek Bagaria Apr 13 '14 at 16:20