Interactive Submodular Set Cover

Details Interactive Submodular Set Cover Interactive Submodular Set Cover

2010-02-17

arxiv.org/abs/1002.3345v2

Computer Science

Learning

15 pages, 1 figure

Scientific paper

We introduce a natural generalization of submodular set cover and exact active learning with a finite hypothesis class (query learning). We call this new problem interactive submodular set cover. Applications include advertising in social networks with hidden information. We give an approximation guarantee for a novel greedy algorithm and give a hardness of approximation result which matches up to constant factors. We also discuss negative results for simpler approaches and present encouraging early experimental results.

Affiliated with

Also associated with

No associations

Rating

Interactive Submodular Set Cover does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Interactive Submodular Set Cover, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interactive Submodular Set Cover will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-52419