| Hongcheng's profileTricksBlogListsNetwork |  Tools  Help |
|
December 03 Submodular FunctionsA submodular function F() mapping a subset of a finite set V to a real number has the following property. For any subsets A and B, F(A) + F(B) >= F(A U B) + F(A ^ B) , where AUB and A^B are union and intersection. A more significant definition is that for any subsets S and R, S is a subset of R, an element e in V, F(S U {e}) - F(S) >= F(R U {e}) -F(R). Here F(S U {e}) - F(S) can be considered as the marginal value of e with respect to S. If -F() is submodular, then F() is called supermudular. If F() is both submodular and supermodular, F() is called modular. Several examples of submodular function. For a graph G(V,E), define F(A) on a subset of V to be the number of edges in the subgraph induced by A. For a directed graph G(V,E) and two vertices s and t, define F(A) on a subset of V/{s,t} to be the number of cut edges between AU{s} and (V-A)U{t}. There are some greedy algorithms to optimize a submodular function. December 01 The fun of solving math riddles07年8月在Google北京实习的时候，我第一次做出了IBM Ponder This的题目，在我的正确提交之前我还提交过一个错误的答案，puzzlemaster很nice的回信指出我的错误，让我很"感动"。从那开始我每个月都上去看题做题。 07年11月的题目很不错，我用了大概1页多A4纸的篇幅描述我的基于图论的构造方法，生怕puzzlemaster不耐烦看还附了一个能生成解的C＋＋程序，最后我的解答被接受了。等到月底公布答案时我被深深的打击了，一个很简单的构造方法描述就那么几行，puzzlemaster真的很nice:) 解答里面还说明这个问题来自另一个数学迷题网站Using your Head is Permitted，于是UyHiP进入我的视线。 慢慢的我发现，IBM Ponder This的题目有时候很无聊，而UyHip的题目更符合我的口味，题目几乎都是跟离散数学，算法，计算复杂度等相关的，而这些正是我的兴趣所在。从07年12月开始，我开始每个月做UyHiP的题目，到今天整整一年了。期间总共13道题目，我做出来了9道。题目都很不错，我最喜欢的是08年1月的题目，可惜我想了一个月都没做出来。那月初的时候我题交了一个复杂的基于欧拉定理的解答，用Latex写了四页，当时很有成就感，最后被指出整个解答赖以成立的引理错了，于是全部解答几乎都是扯淡@#$%$#@。08年7月的题目是我解答出的题目中最难的，我碰巧想到做法的，可能是解答用到的二部图匹配的理论跟算法正好是我比较熟悉的。08年9月的题目我没能成为solver之一，背后还有一个小故事。我猜到了结论，却想了一整天都没想出证明来，我知道这个问题是一个经典问题，应该找得到证明，最后实在忍不住Google了一把，在SIAM的一个期刊上找到一篇论文的一个定理。于是我的ws解答就引用了那篇论文的定理，还把论文下载下来作为解答的附件:)，最后riddle的作者Michael拒绝把我添加到solver列表里面，因为"I can only give credit for an original solution"，还"语重心长"的告诉我"If you ask me, having fun is what solving these riddles is all about."，其实Michael说的很有道理:) |
|
|
