일단 문제

[알고리즘(130.126)]

여기서 x_1, ..., x_M 이 binary variable (0 아니면 1), R_j는 상수, I_i(j) 는 indicator function. 여기서 f를 최대화하는게 NP-hard 임을 보이거나 f를 maximize 하는 알고리즘을 만드는게 문제.

4주동안 진전이 없지 말입니다.

[sh(68.145)]

저도그렇겠네요

[알고리즘(130.126)]

꼭 NP-hard임을 보일 필요는 없고 P 클래스에 안있다는것만 증명해도 되지말입니다.

[sh(68.145)]

P=NP임?왜그렇게만해도댐?

[알고리즘(130.126)]

그게 아니라 걍 저 문제를 푸는 효율적인 알고리즘이 존재 하지 않는다는것만 증명해도 되서 그럼

[sh(68.145)]

그럼디시즌디펜던드한거만보여주면댐?

[알고리즘(130.126)]

어려운 정도로는 디시젼 버젼이나 최적화 버젼이나 똑같을텐데?

[sh(68.145)]

선택에따라최적화가능하다는걸보여주면되는거아닌가해서물어봄

[sh(68.145)]

물론난할줄모릅니다

[알고리즘(130.126)]

선택에 따라라는게 무슨 얘긴지 모르겠는데... integer programming 도 어떤 특정한 폼을 가지고 있으면 polynomial time 안에 풀 수는 있음. 이와 같은게 assignment problem 이고. 하지만 general 케이스는 NP-complete 문제지.

[알고리즘(130.126)]

일단 미천한 학부생 나부랭이 연구 문제기 때문에 코세 성님이라면 하루만에 풀 수 있을거라 생각이 됩니다.

[codesafer(codesafer)]

뭐야 이딴 졸린 문제를 올리면 어떡함.

[codesafer(codesafer)]

문제 읽다 졸뻔 했네. 노잼 노잼해.

[알고리즘(130.126)]

쉬우니까 풀어주십시오.

[sh(68.145)]

지금저건존나마는파서블중에맥시멈섭셋찾는알고리즘내놔라는거아님?그럼비슷한섭셋문제들엔피하드한거증명하듯가는거아니냔헛다리짚기

[sh(68.145)]

맥시멈섭샛이보통디시전에따라옵티멀한구성이나온다는걸보이는게아님?시발몰라존뮨대졸충이라

[알고리즘(130.126)]

당연히 직감적으론 NP-hard 일것 같은데 reduction 하는데 많은 어려움이 있지 말입니다.

[익명(113.216)]

알고리즘//되서->돼서