Select certain number of column elements of a stochastic matrix, maximum one element per rowCount number of ways to place ones in an $M times M$ matrix so that every row and column has $k$ ones?Find the smallest summed distances by uniquely pairing elements of one set to elements of another setMaximize ratio of sumsFind a maximum sum in matrix, subject to special constraintSelect a subset of the columns in $2times n$ matrix, is it easy?Select a set of elements from a 2D matrix, such that each element comes from distinct row and columnIs this problem about picking optimal entries of a matrix NP-complete?Maximizing the sum of selected elements in a matrixIs my interpretation correct?Select K columns from matrix and one element from each row that has maximum sum
Quote to show students don't have to fear making mistakes
As an interviewer, how to conduct interviews with candidates you already know will be rejected?
Are there any tricks to pushing a grand piano?
How to be productive while waiting for meetings to start
Can you take the additional action from the fighter's Action Surge feature before you take your regular action?
What's the correct way to determine turn order in this situation?
Power Adapter for Traveling to Scotland (I live in the US)
Should I reveal productivity tricks to peers?
How does Donald Trump manage to remain so popular over a rather long period of time?
Coffee Grounds and Gritty Butter Cream Icing
Injection from two strings to one string
In 1700s, why was 'books that never read' grammatical?
How to print variable value in next line using echo command
Is negative resistance possible?
Would we have more than 8 minutes of light, if the sun "went out"?
What is the origin of the minced oath “Jiminy”?
How come the Russian cognate for the Czech word "čerstvý" (fresh) means entirely the opposite thing (stale)?
How is the speed of nucleons in the nucleus measured?
Dotted footnote rule
Can/should you swim in zero G?
Unicode-math and declaring symbol font
Can I voluntarily exit from the US after a 20 year overstay, or could I be detained at the airport?
Has Boris Johnson ever referred to any of his opponents as "traitors"?
How to get a smooth, uniform ParametricPlot of a 2D Region?
Select certain number of column elements of a stochastic matrix, maximum one element per row
Count number of ways to place ones in an $M times M$ matrix so that every row and column has $k$ ones?Find the smallest summed distances by uniquely pairing elements of one set to elements of another setMaximize ratio of sumsFind a maximum sum in matrix, subject to special constraintSelect a subset of the columns in $2times n$ matrix, is it easy?Select a set of elements from a 2D matrix, such that each element comes from distinct row and columnIs this problem about picking optimal entries of a matrix NP-complete?Maximizing the sum of selected elements in a matrixIs my interpretation correct?Select K columns from matrix and one element from each row that has maximum sum
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty
margin-bottom:0;
$begingroup$
Consider a $m times n$ Matrix.
Every column represents a class and every row an observation. Every row/observation is a probability distribution, hence every row sums up to 1.
We now want to choose elements $a_i,j$ of the Matrix.
For every column $k_j$ elements have to be chosen, but we can choose just one element per row. The sum of the chosen elements have to be maximized.
I guess this problem is NP-hard. I didn't found an efficient solution.
To prove that, I want to find a reduction from a NP-hard problem to my problem.
Hopefully someone has an idea for a reduction (or an efficient algorithm).
algorithms optimization
edited 2 hours ago
Evil
8,6954 gold badges25 silver badges47 bronze badges
asked 8 hours ago
daniel.golfdaniel.golf
111 bronze badge
New contributor
daniel.golf is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment
|
$begingroup$
Consider a $m times n$ Matrix.
Every column represents a class and every row an observation. Every row/observation is a probability distribution, hence every row sums up to 1.
We now want to choose elements $a_i,j$ of the Matrix.
For every column $k_j$ elements have to be chosen, but we can choose just one element per row. The sum of the chosen elements have to be maximized.
I guess this problem is NP-hard. I didn't found an efficient solution.
To prove that, I want to find a reduction from a NP-hard problem to my problem.
Hopefully someone has an idea for a reduction (or an efficient algorithm).
algorithms optimization
edited 2 hours ago
Evil
8,6954 gold badges25 silver badges47 bronze badges
asked 8 hours ago
daniel.golfdaniel.golf
111 bronze badge
New contributor
daniel.golf is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment
|
$begingroup$
Consider a $m times n$ Matrix.
Every column represents a class and every row an observation. Every row/observation is a probability distribution, hence every row sums up to 1.
We now want to choose elements $a_i,j$ of the Matrix.
For every column $k_j$ elements have to be chosen, but we can choose just one element per row. The sum of the chosen elements have to be maximized.
I guess this problem is NP-hard. I didn't found an efficient solution.
To prove that, I want to find a reduction from a NP-hard problem to my problem.
Hopefully someone has an idea for a reduction (or an efficient algorithm).
algorithms optimization
edited 2 hours ago
Evil
8,6954 gold badges25 silver badges47 bronze badges
asked 8 hours ago
daniel.golfdaniel.golf
111 bronze badge
New contributor
daniel.golf is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
Consider a $m times n$ Matrix.
Every column represents a class and every row an observation. Every row/observation is a probability distribution, hence every row sums up to 1.
We now want to choose elements $a_i,j$ of the Matrix.
For every column $k_j$ elements have to be chosen, but we can choose just one element per row. The sum of the chosen elements have to be maximized.
I guess this problem is NP-hard. I didn't found an efficient solution.
To prove that, I want to find a reduction from a NP-hard problem to my problem.
Hopefully someone has an idea for a reduction (or an efficient algorithm).
algorithms optimization
algorithms optimization
edited 2 hours ago
Evil
8,6954 gold badges25 silver badges47 bronze badges
asked 8 hours ago
daniel.golfdaniel.golf
111 bronze badge
New contributor
daniel.golf is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 2 hours ago
Evil
8,6954 gold badges25 silver badges47 bronze badges
asked 8 hours ago
daniel.golfdaniel.golf
111 bronze badge
New contributor
daniel.golf is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 2 hours ago
Evil
8,6954 gold badges25 silver badges47 bronze badges
edited 2 hours ago
Evil
8,6954 gold badges25 silver badges47 bronze badges
edited 2 hours ago
Evil
8,6954 gold badges25 silver badges47 bronze badges
8,6954 gold badges25 silver badges47 bronze badges
asked 8 hours ago
daniel.golfdaniel.golf
111 bronze badge
New contributor
daniel.golf is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 8 hours ago
daniel.golfdaniel.golf
111 bronze badge
asked 8 hours ago
daniel.golfdaniel.golf
111 bronze badge
111 bronze badge
New contributor
daniel.golf is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
daniel.golf is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment
|
add a comment
|
1 Answer
1
active
oldest
votes
$begingroup$
Duplicate the $j$th column $k_j$ times to reduce to the case in which $k_j = 1$. You are now looking at the assignment problem, which can be solved efficiently.
answered 1 hour ago
Yuval FilmusYuval Filmus
208k15 gold badges202 silver badges369 bronze badges
$endgroup$
add a comment
|
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/4.0/"u003ecc by-sa 4.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
daniel.golf is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f115204%2fselect-certain-number-of-column-elements-of-a-stochastic-matrix-maximum-one-ele%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Duplicate the $j$th column $k_j$ times to reduce to the case in which $k_j = 1$. You are now looking at the assignment problem, which can be solved efficiently.
answered 1 hour ago
Yuval FilmusYuval Filmus
208k15 gold badges202 silver badges369 bronze badges
$endgroup$
add a comment
|
$begingroup$
Duplicate the $j$th column $k_j$ times to reduce to the case in which $k_j = 1$. You are now looking at the assignment problem, which can be solved efficiently.
answered 1 hour ago
Yuval FilmusYuval Filmus
208k15 gold badges202 silver badges369 bronze badges
$endgroup$
add a comment
|
$begingroup$
Duplicate the $j$th column $k_j$ times to reduce to the case in which $k_j = 1$. You are now looking at the assignment problem, which can be solved efficiently.
answered 1 hour ago
Yuval FilmusYuval Filmus
208k15 gold badges202 silver badges369 bronze badges
$endgroup$
Duplicate the $j$th column $k_j$ times to reduce to the case in which $k_j = 1$. You are now looking at the assignment problem, which can be solved efficiently.
answered 1 hour ago
Yuval FilmusYuval Filmus
208k15 gold badges202 silver badges369 bronze badges
answered 1 hour ago
Yuval FilmusYuval Filmus
208k15 gold badges202 silver badges369 bronze badges
answered 1 hour ago
Yuval FilmusYuval Filmus
208k15 gold badges202 silver badges369 bronze badges
answered 1 hour ago
Yuval FilmusYuval Filmus
208k15 gold badges202 silver badges369 bronze badges
208k15 gold badges202 silver badges369 bronze badges
add a comment
|
add a comment
|
daniel.golf is a new contributor. Be nice, and check out our Code of Conduct.
daniel.golf is a new contributor. Be nice, and check out our Code of Conduct.
daniel.golf is a new contributor. Be nice, and check out our Code of Conduct.
daniel.golf is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f115204%2fselect-certain-number-of-column-elements-of-a-stochastic-matrix-maximum-one-ele%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
