지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 저널정보
- 한국경영과학회 Management Science and Financial Engineering International Journal of Management Science Vol.14 No.1
- 발행연도
- 2008.5
- 수록면
- 87 - 90 (4page)
이용수
초록· 키워드
오류제보하기
We show that when a max-cut problem is allowed native-weight edges, to decide if the problem has a cut of a positive weight is NP-hard. This implies that there is no polynomial time algorithm which guarantees a cut whose objective value is no less than 1/p(〈Ⅰ〉) times the optimum for any polynomially computable polynomial p, where 〈Ⅰ〉 denotes the encoding length of an instance Ⅰ.
목차
ABSTRACT
1. Introduction
2. Inapproximability
3. Open problem
References
참고문헌 (4)
참고문헌 신청
1. [학술지(정기간행물)] - Goemans, M.X. / 1995 / Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming / J. ACM 42 : 1115 ~ 1145
2. [학술지(정기간행물)] - Matula, D.W. / 1990 / Sparsest cuts and bottleneck in graphs / Discrete Appl. Math 27 : 113 ~ 123
3. [학술지(정기간행물)] - McCormick, S.T. / 2003 / Easy and difficult objective functions for max cut / Math. Program Ser. B 94 : 459 ~ 466
4. [단행본] - Vazirani, V. V. / 2001 / Approximation algorithms / Springer, Berlin
2. [학술지(정기간행물)] - Matula, D.W. / 1990 / Sparsest cuts and bottleneck in graphs / Discrete Appl. Math 27 : 113 ~ 123
3. [학술지(정기간행물)] - McCormick, S.T. / 2003 / Easy and difficult objective functions for max cut / Math. Program Ser. B 94 : 459 ~ 466
4. [단행본] - Vazirani, V. V. / 2001 / Approximation algorithms / Springer, Berlin
함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
Fractional Surrogate-Knapsack Cuts for Integer Progrms
Management Science and Financial Engineering
2002 .11
-
그래프분할문제
한국경영과학회지
2003 .12
-
Computational Study of Cutting Planes for a Lot-Sizing Problem in Branch-and-Cut Algorithm
한국경영과학회지
2015 .08
-
A Regional Computable General Equilibrium Model for Korea
지역연구
1986 .12
-
Improved Benders Cuts and Lower Bound Cut to Resolve Duality Gap in PPLP
대한경영학회지
2000 .03
-
Cut Tree Approach For Facility Layout Problem
경영과학
1994 .10
-
감세정책의 긍정·부정적 효과관찰
회계정보리뷰
2006 .03
-
Cutting History to Fit: A Study in Motivated Reasoning
The Korean Journal of Policy Studies
2019 .01
-
State Intervention Can Cut Inequality, But the Current Approach Is Wrong
Global Asia
2019 .03
-
A Strong Cutting Plane Algorithm for the Selection Problem with a Resource Constraint
한국경영과학회 학술대회논문집
1993 .01
-
Minimizing total cost in proportionate flow shop with controllable processing times by polynomially solvable 0-1 unconstrained Quadratic Program
한국경영과학회 학술대회논문집
2007 .11
-
특집 : '왜 안 되는데요' 시대의 생활지도 길 찾기/'1cm 더'가 변화는 아니다-NO CUT, 학교에 무엇을 남겼나
중등우리교육
2001 .11
-
MIP formulations for 1.5 -dimensional cutting stock problem
한국경영과학회 학술대회논문집
2016 .04
-
The Growth and Distributive Effects of Corporation Tax: A Computable General Equilibrium Approach
[BOK] Economic Papers
2003 .12
-
[FB7 수리계획 및 최적화(2)] 최대 로트 그룹핑 문제의 복잡성
한국경영과학회 학술대회논문집
2003 .05
-
절사법과 추정
춘계학술대회 발표논문집
2003 .01
-
「NP1ヲNP2トV」の意味構造 : 韓国語構文「NP1를 NP2 라고/로 V」との比較を通じて
동북아시아문화학회 국제학술대회 발표자료집
2009 .10
-
Min-Max Regret Version of an m-Machine Ordered Flow Shop with Uncertain Processing Times
Management Science and Financial Engineering
2015 .05
이 논문의 저자 정보
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2009-325-014771832