Jian Li's Publication

Journal Publications:

A Unified Approach to Ranking in Probabilistic Databases. Jian Li, Barna Saha and Amol Deshpande. The VLDB Journal, 2011.

When LP is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings. Nikhil Bansal, Anupam Gupta, Jian Li, Julian Mestre, Viswanath Nagarajan, Atri Rudra. Algorithimca, 2011.

The load-distance balancing problem. Edward Bortnikov, Samir Khuller, Jian Li, Yishay Mansour and Seffi Naor. Networks, 2010 (accepted).

Algorithms for core stability, core largeness, exactness, and extendability of flow games. Qizhi Fang, R. Fleischer, Jian Li, and Xiaoxun Sun. In Frontier of Math in China, vol 5(1), pp.47-63, 2010. (This journal paper combines this paper and our cocoon07 paper. We fixed some bugs. Now, the thms and pfs should be correct.)

An $O({logn\over loglogn})$ Upper Bound on the Price of Stability for Undirected Shapley Network Design Games. Jian Li.In Information Processing Letter (IPL). 2009. [slides]

More Efficient Algorithms and Analyses for Unequal Letter Cost Prefix-Free Coding. Mordecai Golin, Jian Li. In IEEE Transactions on Information Theory, Volume 54, Issue 8, Aug. Page(s):3412 - 3424, 2008

Refereed Conference Publications:

Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems; Jian Li, and Amol Deshpande; To appear in Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2011), Palm Springs, California, 2011. [ArXiv].

DataSynth: Generating Synthetic Data using Declarative Constraints. Arvind Arasu, Raghav Kaushik, and Jian Li. To appear in the 37th International Conference on Very Large Data Bases (VLDB 2011), Seattle, Wasington, 2011. (Demo)

Data Generation using Declarative Constraints. Arvind Arasu, Raghav Kaushik, and Jian Li. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD 2011), Athens, Greece, 2011.

Sensitivity Analysis and Explanations for Robust Query Evaluation in Probabilistic Databases. Bhargav Kanagal, Jian Li, Amol Deshpande. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD 2011), Athens, Greece, 2011.

Generalized Machine Activation Problems. Jian Li and Samir Khuller. In the ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), San Francisco, USA, 2011. [slides]

Ranking Continuous Probabilistic Datasets. Jian Li and Amol Deshpande. In the 36th International Conference on Very Large Data Bases (VLDB 2010), Singapore, 2010. [slides]

Densest $k$-Subgraph Approximation on Intersection Graphs. Danny Z. Chen, Rudolf Fleischer, Jian Li. In the 8th Workshop on Approximation and Online Algorithms (WAOA 2010). [slides]

New Models and Algorithms for Throughput Maximization in Broadcast Scheduling. Chandra Chekuri, Avigdor Gal, Sungjin Im, Samir Khuller, Jian Li, Richard McCutchen, Benjamin Moseley, Louiqa Raschid. In the 8th Workshop on Approximation and Online Algorithms (WAOA 2010). [slides] [full version]

When LP is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings. Nikhil Bansal, Anupam Gupta, Jian Li, Julian Mestre, Viswanath Nagarajan, Atri Rudra. In the 18th Annual European Symposium on Algorithms (ESA 2010). (Best Paper Award) [slides]

Clustering with Diversity. Jian Li, Ke Yi, Qin Zhang. In the 37th International Colloquium on Automata, Languages and Programming (ICALP 2010),July 5-10, 2010. [full version in arXiv] [slides]

On Computing Compression Trees for Data Collection in Wireless Sensor Networks. Jian Li, Amol Deshpande and Samir Khuller. In the 29th Conference on Computer Communications (INFOCOM 2010), San Diego, USA, 2010 [full version in arXiv] [slides]

Energy Efficient Scheduling via Partial Shutdown. Samir Khuller, Jian Li, Barna Saha. In the ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), Austin, USA , 2010.

A Unified Approach to Ranking in Probabilistic Databases. Jian Li, Barna Saha and Amol Deshpande. In the 35th International Conference on Very Large Data Bases (VLDB 2009), Lyon, France, 2009. (Best Paper Award) [slides long short]

Consensus Answers for Queries over Probabilistic Databases. Jian Li and Amol Deshpande. In the 28th ACM Symposium on Principles of Database Systems (PODS 2009). Providence, USA, 2009 [slides]

Minimizing communication cost in distributed multi-query processing. Jian Li, Amol Deshpande and Samir Khuller. In International Conference on Data Engineering (ICDE2009), Shanghai, China, 2009 [slides]

More Efficient Algorithms and Analyses for Unequal Letter Cost Prefix-Free Coding. Mordecai Golin, Jian Li. In Proceedings of the 18th International Symposium on Algorithms and Computation (ISAAC 2007), Sendai, Japan, 2007. [slides]

Approximating the Maximum Sharing Problem. Amitabh Chaudhary, Danny Z. Chen, Rudolf Fleischer, Jian Li, Xiaobo S. Hu, Michael T. Niemier, Zhiyi Xie, Hong Zhu. In Proceedings of 10th Workshop on Algorithms and Data Structures(WADS 2007) Halifax, Canada, August 15-17, 2007 .

Algorithms for core stability, core largeness, exactness, and extendability of flow games. Qizhi Fang, R. Fleischer, Jian Li, and Xiaoxun Sun. In Proceedings of the 13th Annual International Computing and Combinatorics Conference (COCOON 2007), Banff, Canada, July 16-19, 2007. [slides]

Efficient Algorithms for $k$-Disjoint Paths Problems on DAGs. Rudolf Fleischer, Qi Ge, Jian Li, Hong Zhu. In Proceedings of the 3nd International Symposium on Algorithmic Aspects in Information and Management (AAIM 2007), Portland, USA, 2007.

On approximating the maximum simple sharing problem. Danny Z. Chen, R. Fleischer, Jian Li, Zhiyi Xie, and Hong Zhu. In Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC 2006), Kolkata, December 18-20, 2006. [slides]

Traversing the machining graph. Danny Z. Chen, R. Fleischer, Jian Li, Haitao Wang, and Hong Zhu. In Proceedings of the 14th Annual International Symposium on Algorithms (ESA 2006), Zurich, Switzerland, Sep 11-13, 2006. Springer LNCS. [full version] [slides]

Non-metric multicommodity and multilevel facility location. R. Fleischer, Jian Li, Shijun Tian, and Hong Zhu. In Proceedings of the 2nd International Symposium on Algorithmic Aspects in Information and Management (AAIM 2006), Hong Kong, Jun 20-22, 2006. Springer LNCS 4041, 2006, pp. 138-148.

Approximating spanning trees with inner nodes cost. R. Fleischer, Qi Ge, Jian Li, Shijun Tian, and Haitao Wang. In Proceedings of the 6th International Conference on Parallel and Distributed Computing (PDCAT 2005), Dalian, China, Dec 5-8, 2005, pp. 600-664. [full version]

Some Chinese Papers:

最大简单共享问题的快速近似算法[doc]. 李建,张韬,谢之易,朱洪. 软件学报，2007 (english draft)

关于吹雪机问题的改进近似算法[doc]. 李建,王海涛,朱洪.2006年全国理论计算机科学学术年会. 吉林大学学报（工学版）2007年第1期.

多目标需求的设备选址问题的近似算法[doc]. 田世俊,李建,朱洪.计算机科学,2005.

内点带权生成树近似算[doc]. 王海涛,李建,朱洪.计算机科学 2005.