2022 Developer Survey is open! Take survey.
user avatar
user avatar
user avatar
xiaohan2012
  • Member for 9 years, 6 months
  • Last seen more than a week ago
  • Wuhan, China
4 votes
2 answers
3k views

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

3 votes
2 answers
271 views

Drawbacks of repeating a single pattern matching procedure for many patterns

3 votes
1 answer
7k views

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

3 votes
1 answer
228 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
124 views

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

1 vote
0 answers
104 views

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

1 vote
0 answers
116 views

NP-completeness of maximum-sum subtree with quadratic constraint

1 vote
1 answer
93 views

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

1 vote
0 answers
35 views

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

1 vote
1 answer
2k views

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