Skip to main content
xiaohan2012's user avatar
xiaohan2012's user avatar
xiaohan2012's user avatar
xiaohan2012
  • Member for 11 years, 7 months
  • Last seen more than a month ago
  • Wuhan, China
4 votes
1 answer
7k views

How to implement GREEDY-SET-COVER in a way that it runs in linear time [closed]

4 votes
2 answers
4k views

without triangle inequality, finding good approximate tours for TSP in polynomial time is impossible unless P=NP?

3 votes
2 answers
309 views

Drawbacks of repeating a single pattern matching procedure for many patterns

3 votes
1 answer
270 views

NP-hardness of maximum set cover with even/odd coverage requirement

2 votes
2 answers
2k views

Confusion about finite automata construction in Knuth–Morris–Pratt algorithm

2 votes
1 answer
126 views

NP-COMPLETE:Why say "reduction algorithm computes reduction function"?

1 vote
1 answer
2k views

Approximated TSP: weight of minimum spanning tree less than cost of the optimal tour?

1 vote
0 answers
117 views

NP-hardness of Capacitated Minimum Spanning Tree and Price Collecting Steiner Tree on dag/tree

1 vote
0 answers
121 views

NP-completeness of maximum-sum subtree with quadratic constraint

1 vote
1 answer
97 views

Label coloring to maximize number of "balanced" triangles (NP-hardness)

1 vote
0 answers
42 views

NP-hardness of maximum set cover with element-level submodular function