Last update: Wed Sep 26 02:07:32 MDT 2018
Top |
Symbols |
Numbers |
Math |
A |
B |
C |
D |
E |
F |
G |
H |
I |
J |
K |
L |
M |
N |
O |
P |
Q |
R |
S |
T |
U |
V |
W |
X |
Y |
Z
BibTeX entry
@Article{Khuri:1994:IGR,
author = "Sami Khuri",
title = "Intractability: a geometric representation",
journal = j-SIGCSE,
volume = "26",
number = "1",
pages = "228--232",
month = mar,
year = "1994",
CODEN = "SIGSD3",
DOI = "https://doi.org/10.1145/191033.191127",
ISSN = "0097-8418 (print), 2331-3927 (electronic)",
ISSN-L = "0097-8418",
bibdate = "Sat Nov 17 18:57:24 MST 2012",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/sigcse1990.bib",
abstract = "This paper introduces a geometric representation that
can be applied to illustrate the complexity of some
combinatorial optimization problems. In this work, it
is applied to the 0/1 knapsack problem and to a special
case of a scheduling problem. This representation gives
insight into the difference between tractable and
intractable problems. It can therefore be used as a
stepping stone to compare polynomial (P) and
nondeterministic polynomial (NP) problems, before
venturing into the world of NP-completeness.",
acknowledgement = ack-nhfb,
fjournal = "SIGCSE Bulletin (ACM Special Interest Group on
Computer Science Education)",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J688",
}
Related entries
- applied,
22(4)23,
23(3)5,
24(1)207,
24(1)309,
24(3)35,
24(3)53,
24(4)52,
26(1)339,
26(1)408,
26(3)22,
27(1)1,
27(1)199,
27(4)9,
28(1)363,
28(3)12,
29(1)194,
29(1)243,
29(2)35,
29(3)117,
29(3)120,
30(1)6,
30(1)181,
30(1)227,
30(1)341,
30(3)90,
30(3)139,
30(3)236,
30(4)46,
31(1)242,
31(1)296,
31(3)33,
31(3)64
- case,
22(1)181,
22(3)21,
23(1)108,
23(1)240,
23(1)254,
23(2)60,
23(3)5,
23(4)51,
24(1)97,
24(1)107,
24(1)129,
24(1)220,
24(2)20,
24(3)1,
25(2)57,
26(1)238,
26(1)371,
26(2)61,
26(3)56,
27(1)19,
27(1)102,
27(1)141,
27(1)178,
27(1)302,
27(1)374,
27(2)18,
28(1)319,
28(2)3,
28(2)21,
28(3)55,
28(4)50,
29(1)10,
29(1)82,
29(1)154,
29(1)209,
29(1)330,
29(3)77,
30(1)20,
30(1)25,
30(1)48,
30(1)383,
30(3)125,
30(3)139,
30(3)290,
31(1)78,
31(2)48,
31(2)65,
31(3)17,
31(3)52,
31(3)167,
31(3)180,
31(3)190
- compare,
24(1)113,
24(1)163,
25(4)33,
26(1)80,
27(1)195,
27(2)7,
27(3)21,
28(1)102,
28(1)338,
28(1)353,
28(3)26,
29(1)164,
29(1)301,
30(1)140,
30(3)122,
31(1)122,
31(1)198,
31(1)212,
31(2)65,
31(3)25
- complexity,
22(3)7,
24(1)207,
24(4)11,
25(2)19,
26(1)183,
26(1)349,
27(1)146,
27(1)228,
27(1)253,
27(2)49,
27(3)7,
28(3)5,
29(1)20,
29(3)74,
30(1)10,
30(1)153,
30(1)176,
30(1)317,
30(1)341,
30(3)213,
31(2)65,
31(3)103,
31(3)127
- difference,
23(1)130,
24(1)113,
25(1)78,
26(1)80,
26(1)145,
26(1)258,
26(1)300,
28(1)24,
28(1)37,
29(1)63,
29(3)59,
29(3)80,
29(3)127,
30(1)77,
30(1)171,
30(3)148,
31(1)198,
31(1)217,
31(2)60,
31(2)84
- geometric,
24(4)27,
27(4)35,
30(1)97
- give,
22(3)34,
23(2)9,
23(3)2,
24(1)259,
24(2)59,
24(4)35,
25(2)31,
26(1)83,
26(1)203,
26(2)36,
26(4)17,
27(1)159,
27(1)228,
27(4)5,
27(4)21,
28(1)155,
28(2)49,
29(1)96,
29(1)101,
29(1)150,
29(1)204,
29(1)272,
29(2)23,
29(3)57,
29(3)74,
29(3)103,
29(3)136,
30(1)40,
30(1)117,
30(1)212,
30(1)287,
30(3)162,
30(3)166,
30(4)32,
31(1)227,
31(1)237,
31(1)341,
31(2)60,
31(2)73,
31(3)44,
31(3)135,
31(3)151,
31(4)4,
31(4)66
- illustrate,
22(3)34,
24(1)76,
24(1)207,
24(3)35,
24(3)53,
26(1)83,
26(1)238,
26(1)366,
26(2)19,
26(3)29,
27(1)126,
27(1)199,
27(1)263,
27(1)340,
28(1)107,
28(1)160,
28(1)185,
28(1)256,
28(1)343,
28(1)348,
28(2)62,
28(4)36,
29(1)126,
29(1)135,
29(1)238,
29(1)243,
29(3)45,
30(1)48,
30(1)207,
30(1)217,
30(1)277,
30(3)171,
30(3)243,
31(1)53,
31(1)87,
31(1)136,
31(1)286,
31(1)367,
31(2)78,
31(3)198,
31(3)206
- insight,
24(1)147,
24(2)7,
26(1)150,
26(4)59,
27(1)355,
28(1)256,
28(2)37,
28(3)55,
29(1)272,
30(1)140,
30(3)86,
31(1)127,
31(2)62,
31(3)5
- introduce,
22(2)42,
22(3)25,
22(4)25,
23(1)324,
23(2)9,
23(2)24,
24(1)202,
25(2)59,
25(4)5,
25(4)21,
26(1)102,
26(1)131,
26(1)213,
26(1)290,
26(1)366,
26(4)56,
27(1)56,
27(1)141,
27(2)25,
27(3)15,
27(3)34,
28(1)78,
28(1)88,
28(1)217,
28(2)31,
28(3)12,
28(3)45,
29(1)258,
29(1)282,
29(1)330,
29(1)345,
29(2)39,
29(3)14,
29(3)27,
29(3)91,
30(1)68,
30(1)161,
30(1)194,
30(1)237,
30(1)317,
30(1)326,
30(1)365,
30(2)31,
30(3)5,
30(3)25,
30(3)81,
30(3)213,
30(4)42,
31(1)110,
31(1)141,
31(1)247,
31(2)86,
31(3)64,
31(3)167,
31(3)182,
31(3)186,
31(3)189
- Khuri, Sami,
26(1)339,
28(z)25,
30(1)232,
31(1)227,
31(1)252
- knapsack,
27(1)56
- nondeterministic,
31(1)336
- optimization,
31(2)28
- polynomial,
24(1)225
- representation,
24(4)27,
26(1)203,
26(2)2,
27(1)19,
27(1)66,
27(1)163,
27(1)297,
27(1)331,
28(1)348,
28(z)234,
29(1)20,
29(1)30,
29(2)35,
30(1)77,
30(3)69,
30(3)94,
30(3)102,
31(1)110,
31(2)17,
31(3)95,
31(3)131
- scheduling,
22(1)89,
24(1)129,
27(1)186,
28(1)353,
29(1)53,
30(3)185,
30(3)310,
31(1)227,
31(1)311,
31(3)186
- special,
22(1)253,
22(1)256,
22(3)39,
23(2)60,
24(1)197,
27(1)53,
27(1)56,
27(1)331,
28(1)102,
28(1)353,
29(3)65,
29(4)45,
30(1)222,
30(1)307,
30(3)77,
30(3)223,
31(3)56,
31(3)187,
31(3)199
- therefore,
26(4)59,
27(1)24,
28(2)3,
30(1)312,
30(3)59,
30(4)18,
31(1)203,
31(2)78,
31(3)107,
31(3)203,
31(4)50
- tractable,
26(1)281
- world,
22(1)143,
22(1)216,
24(1)107,
24(1)202,
24(1)240,
24(1)246,
25(1)213,
26(1)97,
26(1)102,
26(1)218,
27(1)146,
27(1)178,
27(3)21,
28(1)160,
28(1)175,
28(1)185,
28(1)195,
28(1)280,
28(1)290,
28(2)3,
28(z)1,
28(z)20,
28(z)57,
28(z)66,
28(z)101,
28(z)218,
28(z)231,
29(1)39,
29(1)96,
29(1)116,
29(1)199,
29(1)384,
29(3)8,
29(3)37,
29(3)54,
29(3)59,
29(3)71,
29(3)127,
30(1)40,
30(1)107,
30(1)145,
30(1)176,
30(1)194,
30(1)222,
30(1)227,
30(1)277,
30(1)341,
30(1)345,
30(1)382,
30(3)5,
30(3)51,
30(3)139,
30(3)189,
30(3)209,
30(3)275,
30(3)279,
30(3)290,
30(4)4,
30(4)39,
31(1)146,
31(1)174,
31(1)311,
31(2)73,
31(3)60,
31(3)119,
31(3)147,
31(3)182,
31(3)206