<p>Let $k$ be the finite number of agents you're allowed to choose. If there are no critical services, finding the set of $k$ agents that maximize the number of non-critical services provided is equivalent to Max-$k$-Cover, which can't be approximated better than $1-1/e$ unless P=NP. So for an exact solution, you'll have to use something capable of solving NP-hard problems.</p>

<p>If you'd be happy with an approximation, you're in luck. The constraint that you have to choose $k$ agents such that there are sufficiently many of them providing each service is a matroid constraint. <a href="http://www.google.com/url?sa=t&amp;source=web&amp;cd=1&amp;ved=0CBsQFjAA&amp;url=http://www.cs.uiuc.edu/~chekuri/papers/submod_max.pdf&amp;rct=j&amp;q=maximizing%20a%20submodular%20function%20under%20matroid%20constraints&amp;ei=-dT0TenSBcTiiALE9ciCBw&amp;usg=AFQjCNFyszXBfqqx-5JpRg2PvBFYjzsMsg&amp;cad=rja" rel="nofollow">This paper</a> shows how to achieve a $1-1/e$ approximation on set cover problems under a matroid constraint.</p>

<p>If you want something simpler to implement, the matroid greedy algorithm gives a $1/2$ approximation on submodular set functions. So you just need to repeatedly choose the agent that provides the most new non-critical services, after at each step removing from consideration any agent whose choice would prevent you from providing enough of each critical service before reaching $k$ agents. If each agent provides unique non-critical services, you're just maximizing a weight function over a matroid, so the greedy algorithm gives an exact solution.</p>

CC BY-SA 3.0
2011-06-13T17:28:58.607Z
Thanks Dave. I'd prefer an exact solution, but at least I now have somewhere to start looking.
David
CC BY-SA 3.0
2011-06-14T17:37:45.920Z
Your problem is NP-hard, so if you want an exact solution, you'll need to mess around with something capable of solving NP-hard problems. If you're bothered by having to formulate 3SAT instances, perhaps you should look into integer linear programming.
Dave
CC BY-SA 3.0
2011-06-12T15:47:22.163Z
2011-06-12T15:47:22.163Z
Dave
<p>I've got a specific problem, but I'm not sure where to look to solve it:</p>

<p>In the context of my application, there are critical services, non-critical services, and agents which provide exactly one critical service and one or more non-critical services. I must choose from the collection of all agents (with replacement) a finite number of agents, such that each critical service is provided by a certain number of agents. This is straightforward. However, I have the secondary objective that I would like the set I choose to also provide as many different non-critical services as possible.</p>

<p>I'm sure this can be done via SAT, but I don't really want to mess around with NP-complete solvers. The goal for either kind (critical or not) of the services could be constructed as a network flow problem and solved in a straightforward way, but I can't seem to merge them, even as a multi-commodity network flow.</p>

<p>Has anyone seen this problem before, or something embarrassingly similar? I'd really appreciate a pointer to where I could start looking for solutions.</p>

<p>-- David</p>

CC BY-SA 3.0
2011-06-11T06:09:22.743Z
The secondary objective alone seems to be equivalent to set cover, which is NP-hard.
Dave
CC BY-SA 3.0
2011-06-11T08:18:31.857Z
I think [linear programming](http://en.wikipedia.org/wiki/Linear_programming) can help you.
Sadeq Dousti
<ds.algorithms><reference-request>
Name this satisfiability problem?
David
# Name this satisfiability problem?

(Asked by: username_0 on 2011-06-11)

I've got a specific problem, but I'm not sure where to look to solve it:

In the context of my application, there are critical services, non-critical services, and agents which provide exactly one critical service and one or more non-critical services. I must choose from the collection of all agents (with replacement) a finite number of agents, such that each critical service is provided by a certain number of agents. This is straightforward. However, I have the secondary objective that I would like the set I choose to also provide as many different non-critical services as possible.

I'm sure this can be done via SAT, but I don't really want to mess around with NP-complete solvers. The goal for either kind (critical or not) of the services could be constructed as a network flow problem and solved in a straightforward way, but I can't seem to merge them, even as a multi-commodity network flow.

Has anyone seen this problem before, or something embarrassingly similar? I'd really appreciate a pointer to where I could start looking for solutions.

-- David

**Tags:** ds.algorithms, reference-request
> **Comments:**
> **username_1**: The secondary objective alone seems to be equivalent to set cover, which is NP-hard.  
> **username_2**: I think [linear programming](http://en.wikipedia.org/wiki/Linear_programming) can help you.  

---

## 1 answers

### Answer by username_1 on 2011-06-12. Score: 2

Let $k$ be the finite number of agents you're allowed to choose. If there are no critical services, finding the set of $k$ agents that maximize the number of non-critical services provided is equivalent to Max-$k$-Cover, which can't be approximated better than $1-1/e$ unless P=NP. So for an exact solution, you'll have to use something capable of solving NP-hard problems.

If you'd be happy with an approximation, you're in luck. The constraint that you have to choose $k$ agents such that there are sufficiently many of them providing each service is a matroid constraint. [This paper](http://www.google.com/url?sa=t&source=web&cd=1&ved=0CBsQFjAA&url=http://www.cs.uiuc.edu/~chekuri/papers/submod_max.pdf&rct=j&q=maximizing%20a%20submodular%20function%20under%20matroid%20constraints&ei=-dT0TenSBcTiiALE9ciCBw&usg=AFQjCNFyszXBfqqx-5JpRg2PvBFYjzsMsg&cad=rja) shows how to achieve a $1-1/e$ approximation on set cover problems under a matroid constraint.

If you want something simpler to implement, the matroid greedy algorithm gives a $1/2$ approximation on submodular set functions. So you just need to repeatedly choose the agent that provides the most new non-critical services, after at each step removing from consideration any agent whose choice would prevent you from providing enough of each critical service before reaching $k$ agents. If each agent provides unique non-critical services, you're just maximizing a weight function over a matroid, so the greedy algorithm gives an exact solution.

> **Comments:**
> **username_0**: Thanks Dave. I'd prefer an exact solution, but at least I now have somewhere to start looking.  
> **username_1**: Your problem is NP-hard, so if you want an exact solution, you'll need to mess around with something capable of solving NP-hard problems. If you're bothered by having to formulate 3SAT instances, perhaps you should look into integer linear programming.  

---

