Questions tagged [combinatorics]
For questions about the study of finite or countable discrete structures, especially how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.
9 questions
0
votes
0
answers
72
views
A set Counting Problem
Consider three positive integers $W, u (<W), v (<W)$ and all $u$-sized subsets of $[W]=\{1,2,...,W\}$. I have to make a collection $\mathcal{L}$ of $v$-sized subsets of $[W]$. with the following ...
1
vote
2
answers
890
views
How to solve assignment problem with additional constraints?
The assignment problem is defined as:
Let there be n agents and m tasks. Any agent can be assigned to perform any task, incurring some costs that may vary depending on the agent-task assignment. We ...
- 21
6
votes
1
answer
287
views
Use GA for Assignment Problem?
I have a two-objective assignment problem that appears to converge really slowly to a solution.
Even if we just have 1 objective that minimizes costs, it appears to be very slow for a worker-task ...
- 179
5
votes
0
answers
149
views
How many clues make Sudoku polynomial
Consider a $n^2 \times n^2$ grid sudoku.
Define a clue to be composed of a coordinate $x$ and $y$ of the grid and a value $z$.
The goal is given $n$ and a set of clues, to find one solution to the ...
- 303
1
vote
1
answer
312
views
Minimum vertex cover and linear programming 2
This is a modified version of the algorithm that I have proposed here.
Suppose we have a graph G. Consider the minimum vertex cover problem of G formulated as a linear programming problem, that is for ...
9
votes
1
answer
392
views
Specific algorithms to compute the LP-relaxation of the Set-Cover problem
One of the most commonly known combinatorial problems is the set cover problem, which states that given a collection of sets $S = \{s_1, \dots, s_m\}$ and a universe of elements $U = \bigcup_{i=1}^m ...
- 2,130
4
votes
1
answer
393
views
Combinatorial Optimisation, Allocation problem
I am trying to solve a problem (in pyspark/ python) where I need to find two distinct values to allocate, and how to allocate them in a network of stores.
The two distinct values can only be integer ...
- 43
7
votes
1
answer
1k
views
Minimum vertex cover and linear programming
Suppose we have a graph G. Consider the minimum vertex cover problem of G formulated as a linear programming problem, that is for each vertex $v_{i}$ we have the variable $x_{i}$, for each edge $v_{i}...
11
votes
3
answers
909
views
Modeling the Choose function
In statistics, one often encounters the choose function ${x \choose y}$ which encodes the number of ways of choosing $y$ items from a set of $x$ items. How would one go about modeling a choose ...
- 725