Last update: August 31 2009 05:42:47.

PDF version
Department of Computer Science
365 Fifth Avenue	Tel: (212)817-7222
The Graduate Center, CUNY	yfeng(A)cs.gc.cuny.edu
New York, NY 10016	http://web.cs.gc.cuny.edu/~yfeng
Education Ph.D. Computer Science, The Graduate Center, City University of New York, Spring 2010 (Expected) M. Phil. enroute Computer Science, The Graduate Center, City University of New York. Sep. 2008 B.Eng. Computer Science and Technology, Nankai University, China, Jun. 2003 GPA: Undergraduate 87.6/100 Graduate 3.88/4.0 Research Interest: Theoretical aspect of network algorithms; Experimental algorithms. Publications Papers co-authored with Amotz Bar-Noy are alphabetically ordered in authorship. Amotz Bar-Noy, Panagiotis Cheilaris, Yi Feng, and Mordecai J. Golin, Paging Mobile Users in Cellular Networks: Optimality versus Complexity. submitted to IEEE Trans. on Netw.. Amotz Bar-Noy, Panagiotis Cheilaris, and Yi Feng, Searching Mobile Users with Congection Cost. Manuscript.. Amotz Barnoy, Yi Feng, Matthew P. Johnson, and Ou Liu, When to Reap and When to Sow: Lowering Peak Usage With Realistic Batteries. Workshop on Experimental Algorithms (WEA).pp:194-207 (2008). Amotz Bar-Noy, Yi Feng, and Mordechai J. Golin, Efficiently and Optimally Paging Mobile Users. 26th IEEE International Conference on Computer Communications (INFOCOM), pp:1910-1918 (2007). Yi Feng, Zhigang Zhu, and Jizhong Xiao. Self-Localization of a Heterogeneous Multi-Robot Team in Constrained 3D Space. Proceedings on IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp:1343-1350 (2007). Yi Feng, Zhigang Zhu, and Jizhong Xiao. Heterogeneous Multi-Robot Localization in Unknown 3D Space. Proceedings on the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp:4533-4538 (2006). Skills: Programming Languages: C, C++, Java, SQL, Matlab, Mathematica, CPLEX Operating Systems (Services): Red Hat Enterprise Linux 4/5, Ubuntu, Windows Server 2003, Windows XP and Vista Research Experience Searching "Mobile" Data 06/2005 - present PI: Prof. Amotz Bar-Noy The Graduate Center, CUNY The combinatorial optimization problem: M≥1 tokens, T1,...,TN, are placed in N≥1 boxes B1,...,BN, and then the boxes are locked. Each token Ti is placed in one of the boxes and is associated with a vector of probabilities pi1,...,piN where pij is the probability of token Ti to be placed at box Bj. Each token may be associated with a different vector. All the probabilities are independent and ∑j=1N pij=1 for each 1≤i≤M. A searcher is looking for either all the tokens, some of them, or one of them. When the searcher unlock box Bj, it collects all the tokens in this box. The cost of unlocking box Bj is cj. Without loss of generality, it is assumed that ∑j=1N cj=1. The searcher conducts its search in rounds and must accomplish its task in at most D(≥1) rounds. In each round, the searcher may unlock any set of locked boxes concurrently. The optimization goal is to minimize the expected cost of unlocking boxes until the task is accomplished. The original motivation: Mobile users (tokens) are roaming in a zone of N cells (boxes). Users do not update their location unless they leave the zone. When a call arrives to one of the users, the system (searcher) needs to find the exact cell in which the user is located (the M=1 case). The system pages the cells in rounds, where in each round a subset of the cells are paged. The search terminates once the user is found. The system must find the user in no more than D rounds and its goal is to minimize the expected number of paged cells until the user is found. For a Conference Call, the system needs to find M>1 users. For a Yellow Page search, the system needs to find one out of M>1 users. Theoretical results: This problem attracted a lot of attention in the recent decade for the special case of one user (M=1) in which all the costs wis are the same. The case can be solved in Θ(N2D) time through dynamic programming for any value of D rounds. We reduced the complexity of the dynamic programming algorithm to Θ(ND). When wis are different, we proved the problem is strongly NP-hard for N > D >2 even ci=pi. We showed PTAS solution when pi=ci. For arbitrary cis, we proved a natural heuristic is an 8/7+ε-approximation and 8/7 is attainable when D=2. We also show optimal solution when D=N. The hardness of yellow page problem is unknown. For D=N, we showed a lower bound 2 and an upper bound 4 of a greedy heuristic. Simulations: We obtained 171929 appearances of 996 users in 5625 cells. Using cross validation, we showed the user location and cell congestion follow Zipf distribution. We tested the performance of our heuristics and the running time of optimal algorithms / heuristics on real machine. Services Student Representative, Executive Committee, PhD Program in Computer Science, City University of New York. May 2008 - present Honors Doctoral Student Research Grant, The Graduate Center, CUNY 2007, 2009 University Fellowship, The Graduate Center, CUNY 2006, 2007, 2008 Science Fellowship, The Graduate Center, CUNY 2004-2006, 2008 References Amotz Bar-Noy, Professor, Department of Computer Science City University of New York. 365 Fifth Avenue, New York, NY 10016. amotz@sci.brooklyn.cuny.edu Theodore Brown, Professor and E.O., Department of Computer Science City University of New York. 365 Fifth Avenue, New York, NY 10016. tbrown@gc.cuny.edu