All Questions
70
questions
0
votes
0
answers
161
views
NP completeness of a variant of assignment problem
I have the following variant of assignment problem:
Suppose we have $m$ machines and $n$ jobs. Each machine is capable of doing a subset of jobs and each machine $i$ has capacity $C_i$. Each job $j$ ...
- 422
2
votes
0
answers
45
views
Does submodularity provide guarantees for "backwards" greedy elimination algorithms?
The submodularity condition, besides having a definition that "makes sense," is also nice because it offers guarantees for the maximum coverage problem (as well as the related set cover ...
- 390
1
vote
1
answer
637
views
Change making problem - Pearson algorithm to check the optimality of greedy solution
This is a question regarding the common version of the Change making problem, which is:
"how can a given amount of money be made with the least number of coins of given denominations (we have ...
- 113
12
votes
1
answer
331
views
Searching radioactive balls
There are $n$ balls, and $m$ of them are radioactive. You can test any set of balls and find out whether there is at least one radioactive ball in this set (but it is impossible to know how many of ...
- 15.7k
1
vote
0
answers
11
views
Find Extremal Point over a Set of all Simple Cycle in a Directed Graph
Dearl all,
I recently stumbled across an interesting combinatorial problem and was wondering if someone here has faced something similar and would help me get a head start.
Problem Defintion
Let G be ...
- 11
1
vote
1
answer
259
views
Find a maximum-weight matching in general graph with constrained cardinality
Let $G=(V,E)$ be a general graph, where edges have weights $w(e)$ and $|V|$ is even.
One of the classic problem is to find a maximum-weight perfect matching (MWPM) of the graph G.
The MWPM problem can ...
- 13
0
votes
0
answers
26
views
Approximating global extrema with the extrema of subsets of parameters
I don't have a particularly strong background on math;
I have a function of many boolean parameters $\theta_i$ :
$$ y = f( \theta_1 , ...., \theta_n ) $$
And I look for the values of the parameters ...
- 13
0
votes
2
answers
70
views
Maximizing a combinatorial identity
So here is my problem. If we have a vector $\textbf{x}=(x_1,...,x_n)$ where $x_j \in \mathbb{N}$ for each $j \in \{1,...,n\}$, then is there a way to maximize the value of the following combinatorial ...
user830143
4
votes
0
answers
103
views
Reducing column ranges of a matrix
I'm looking for an algorithm to reduce the sum of column ranges in a sparse integer matrix by subtracting $1$ from all nonzero elements in a subset of the rows.
Let $R = 1, \ldots, m$ and $C = 1, \...
- 146
0
votes
1
answer
84
views
Optimal planning for mail box servicing and processing (for a message queue online consumer scheduling)
Consider I have $n$ mail boxes $\{m_1, m_2, \dots, m_n \}$. Messages come to each box at different rate/sec e.g., mail box $n$ has an arrival rate of messages equal say 5 per second. In general, let ...
- 131
0
votes
0
answers
57
views
$m$ players choosing from $n$ integers game
$m$ players play a game in which they pick distinctive integers in the range $0:n$ one after another. Then we pick a random integer from $0:n$. Whoever is closest to our pick wins.
What's the optimal ...
0
votes
1
answer
78
views
How to solve this mathematical programming problem?
Suppose each point in the interval $[0,1]$ has some of a set of $N$ properties. The total length of the intervals with property $i$ is $x_i$ ($0\le x_i \le 1$).
Questions:
What is the maximum and ...
- 213
1
vote
0
answers
71
views
Worst-case minimization of size of intersection of an offset set with a given set
Consider the set of first $N$ natural numbers i.e., $S_N$ = $\{1,2,3, \dots,N\}$. Let $S^k$ be a finite subset of $S_N$, where $|S^k|$ = $k$. We define another set $O$ whose elements $\in$ $\{0,1,2,\...
- 104
11
votes
2
answers
563
views
Pouring water from bottles
There are three buckets of size $x_1, x_2$, and $x_3$ liters (positive, but not necessarily integers), and some bottles, possibly of different sizes, containing a total of $x_1+x_2+x_3$ liters of ...
- 1,971
0
votes
0
answers
40
views
Is there any classic combinatorial optimization similar to my problem?
everyone.
I try to solve a non-convex optimization problem as follows:
$$
\min_{\mathbf{x}} f\left ( \mathbf{x} \right )
$$
subject to
$$
\sum_{i \in \mathcal{S}} x_{i} = N,
$$
$$
0\leq x_{i}\leq \...
- 1