There is a complete graph $G$ with $n$ vertices and each edge has a distinct weight.Is there an efficient (not necessarily optimal) algorithm to select $k$ vertices from the graph $G$, such that the total cost of the min-spanning tree of the selected $k$ vertices will be highest?In my case, $n$ is around 1000, and $k$ around 100.
Pick a subgraph that maximizes the total cost of min-spanning tree among all subgraphs of the same size
algorithms;graph theory;graphs;optimization
Your problem is NP-complete, so you should not expect to find any efficient algorithm for it.If we could solve your problem efficiently, we could solve the $k$-clique problem, too.  Let $G$ be an unweighted, undirected graph; we are curious whether it has a $k$-clique.  Translate it into an instance of your problem by making each edge have weight 2, and then for each pair of vertices $u,v$ that are not connected by an edge, add a new edge of weight 1.  Now ask for the solution to your problem.  Notice that there exists a way to select $k$ vertices such that the corresponding spanning tree has cost $2k$, if and only if $G$ has a $k$-clique (if $G$ does not have a $k$-clique, no matter how you select $k$ vertices, the cost of the spanning tree will always be $\le 2k-1$).Since the $k$-clique problem is NP-complete, your problem is NP-complete, too.  Therefore, we cannot expect an efficient solution for your problem, when $k$ is arbitrary.