# caozhu

Beijing, China

Age: 25

I'm a fourth year undergraduate student in Tsinghua University.

 Apr 1 awarded Commentator Apr 1 comment Exactly solvable but non-trivial integrality gapI'm afraid the answer would probably be no. Any familiar problems with non-trivial integrality gap are NP, such as vertex cover. In fact, for polynomial time solvable problems, one can manually construct an LP that gives the answer while having no integrality gaps. Apr 1 awarded Informed Apr 1 awarded Editor Nov 20 comment Why is HAMILTONIAN CYCLE so different from PERMANENT?I have a question a bit off the topic. May I ask why PERMANENT is in P over the boolean semiring? I'm not aware of such an algorithm. Sep 24 awarded Autobiographer Sep 24 awarded Autobiographer Sep 24 awarded Autobiographer Sep 24 awarded Autobiographer Sep 24 awarded Autobiographer Sep 24 awarded Autobiographer Sep 24 awarded Autobiographer Apr 22 awarded Popular Question Mar 23 comment Extensions of Sylvester's inertia law?The problem description is not at all clear. How is $n$ defined for example. And is all the coordinate of $M$ belongs to the same space so that $F$ can be well defined. A more precise formulation of the problem would be adding the condition that $M:R^n \times \dots \times R^n \to R$. Feb 21 comment $NP$-completeness of recognizing the difference of two permutationsWhy not ask Peter directly? @Peter Feb 20 comment Crown Rule Reduction In Parameterized Complexity - Vertex Cover - Notion QuestionFrom your description, I don't see any errors. Feb 20 comment Sorting using read-only stacksI don't think it's possible to print the sorted list given the allowed operations. According to the register machine model, the first entry printed must be one of the first element of some register. Thus if the smallest element is at the end of one register, we can't possibly print it out firstly as it should be. Nov 19 awarded Popular Question Jun 16 comment Proving greedy algorithm is optimal for a scheduling problem@NAg: I don't quite understand what you mean. Could you be more specific on how you do the induction? Jun 16 comment Proving greedy algorithm is optimal for a scheduling problem@SureshVenkat: For example, task sequence 101010101010 makes greedy algorithm with k=0 a sub optimal solution. At the end of the algorithm, the two queues will be $100000$ and $111110$, making the cost $(1)+(1+2+3+4+5)=16$. When $k=3$ or $k=4$, two queues will be $101000$ and $111010$, making the cost $(1+3)+(1+2+3+5)=15<16$. Thus $k=0$ is suboptimal in this case.