<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-04-11T15:01:49.710Z
Is nonoverlapping hyperspheres a subset of this domain? Overlap by two hyperspheres would mean an even cover.
Chad Brewbaker
CC BY-SA 3.0
2014-04-11T15:07:17.470Z
1) [Rom Pinchasi, "Points covered an odd number of times by translates" (2012)](http://www2.math.technion.ac.il/~room/ps_files/odd.pdf); 2) [Thornton et al. Odd/Even Cube Covering for Minimizing ESOP Circuits](http://lyle.smu.edu/~mitch/ftp_dir/pubs/ssst00.ps)
Marzio De Biasi
CC BY-SA 3.0
2014-04-11T15:15:29.850Z
... 3) [Algebraic Problems in Computational Complexity](http://www.tcs.tifr.res.in/~pgdsen/pages/phdthesis/thesis.pdf) ... *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
CC BY-SA 3.0
2014-04-11T15:26:10.450Z
... 4) [Cover with eulerian graphs](http://www.sciencedirect.com/science/article/pii/S0095895603000686): 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
CC BY-SA 3.0
2014-04-13T16:20:09.923Z
Writing down the complete problem will increase the chance of obtaining answers. Thanks
Vivek Bagaria
<set-cover><approximation><covering-problems>
Do there exist "odd times" cover problems and what do we know about their approximability?
Dennis Weyland
# Do there exist "odd times" cover problems and what do we know about their approximability?

(Asked by: username_0 on 2014-04-11)

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.

**Tags:** set-cover, approximation, covering-problems

> **Comments:**
> **username_1**: Is nonoverlapping hyperspheres a subset of this domain? Overlap by two hyperspheres would mean an even cover.  
> **username_2**: 1) [Rom Pinchasi, "Points covered an odd number of times by translates" (2012)](http://www2.math.technion.ac.il/~room/ps_files/odd.pdf); 2) [Thornton et al. Odd/Even Cube Covering for Minimizing ESOP Circuits](http://lyle.smu.edu/~mitch/ftp_dir/pubs/ssst00.ps)  
> **username_2**: ... 3) [Algebraic Problems in Computational Complexity](http://www.tcs.tifr.res.in/~pgdsen/pages/phdthesis/thesis.pdf) ... *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$)  
> **username_2**: ... 4) [Cover with eulerian graphs](http://www.sciencedirect.com/science/article/pii/S0095895603000686): 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  
> **username_3**: Writing down the complete problem will increase the chance of obtaining answers. Thanks  

---

## 0 answers

