5 Search Results for "Shi, Lei"


Document
New Bounds on Augmenting Steps of Block-Structured Integer Programs

Authors: Lin Chen, Martin Koutecký, Lei Xu, and Weidong Shi

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)


Abstract
Iterative augmentation has recently emerged as an overarching method for solving Integer Programs (IP) in variable dimension, in stark contrast with the volume and flatness techniques of IP in fixed dimension. Here we consider 4-block n-fold integer programs, which are the most general class considered so far. A 4-block n-fold IP has a constraint matrix which consists of n copies of small matrices A, B, and D, and one copy of C, in a specific block structure. Iterative augmentation methods rely on the so-called Graver basis of the constraint matrix, which constitutes a set of fundamental augmenting steps. All existing algorithms rely on bounding the 𝓁₁- or 𝓁_∞-norm of elements of the Graver basis. Hemmecke et al. [Math. Prog. 2014] showed that 4-block n-fold IP has Graver elements of 𝓁_∞-norm at most 𝒪_FPT(n^{2^{s_D}}), leading to an algorithm with a similar runtime; here, s_D is the number of rows of matrix D and 𝒪_FPT hides a multiplicative factor that is only dependent on the small matrices A,B,C,D, However, it remained open whether their bounds are tight, in particular, whether they could be improved to 𝒪_FPT(1), perhaps at least in some restricted cases. We prove that the 𝓁_∞-norm of the Graver elements of 4-block n-fold IP is upper bounded by 𝒪_FPT(n^{s_D}), improving significantly over the previous bound 𝒪_FPT(n^{2^{s_D}}). We also provide a matching lower bound of Ω(n^{s_D}) which even holds for arbitrary non-zero lattice elements, ruling out augmenting algorithm relying on even more restricted notions of augmentation than the Graver basis. We then consider a special case of 4-block n-fold in which C is a zero matrix, called 3-block n-fold IP. We show that while the 𝓁_∞-norm of its Graver elements is Ω(n^{s_D}), there exists a different decomposition into lattice elements whose 𝓁_∞-norm is bounded by 𝒪_FPT(1), which allows us to provide improved upper bounds on the 𝓁_∞-norm of Graver elements for 3-block n-fold IP. The key difference between the respective decompositions is that a Graver basis guarantees a sign-compatible decomposition; this property is critical in applications because it guarantees each step of the decomposition to be feasible. Consequently, our improved upper bounds let us establish faster algorithms for 3-block n-fold IP and 4-block IP, and our lower bounds strongly hint at parameterized hardness of 4-block and even 3-block n-fold IP. Furthermore, we show that 3-block n-fold IP is without loss of generality in the sense that 4-block n-fold IP can be solved in FPT oracle time by taking an algorithm for 3-block n-fold IP as an oracle.

Cite as

Lin Chen, Martin Koutecký, Lei Xu, and Weidong Shi. New Bounds on Augmenting Steps of Block-Structured Integer Programs. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 33:1-33:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ESA.2020.33,
  author =	{Chen, Lin and Kouteck\'{y}, Martin and Xu, Lei and Shi, Weidong},
  title =	{{New Bounds on Augmenting Steps of Block-Structured Integer Programs}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{33:1--33:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.33},
  URN =		{urn:nbn:de:0030-drops-128994},
  doi =		{10.4230/LIPIcs.ESA.2020.33},
  annote =	{Keywords: Integer Programming, Graver basis, Fixed parameter tractable}
}
Document
Smart Contract Execution - the (+-)-Biased Ballot Problem

Authors: Lin Chen, Lei Xu, Zhimin Gao, Nolan Shah, Yang Lu, and Weidong Shi

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)


Abstract
Transaction system build on top of blockchain, especially smart contract, is becoming an important part of world economy. However, there is a lack of formal study on the behavior of users in these systems, which leaves the correctness and security of such system without a solid foundation. Unlike mining, in which the reward for mining a block is fixed, different execution results of a smart contract may lead to significantly different payoffs of users, which gives more incentives for some user to follow a branch that contains a wrong result, even if the branch is shorter. It is thus important to understand the exact probability that a branch is being selected by the system. We formulate this problem as the (+-)-Biased Ballot Problem as follows: there are n voters one by one voting for either of the two candidates A and B. The probability of a user voting for A or B depends on whether the difference between the current votes of A and B is positive or negative. Our model takes into account the behavior of three different kinds of users when a branch occurs in the system -- users having preference over a certain branch based on the history of their transactions, and users being indifferent and simply follow the longest chain. We study two important probabilities that are closely related with a blockchain based system - the probability that A wins at last, and the probability that A receives d votes first. We show how to recursively calculate the two probabilities for any fixed n and d, and also discuss their asymptotic values when n and d are sufficiently large.

Cite as

Lin Chen, Lei Xu, Zhimin Gao, Nolan Shah, Yang Lu, and Weidong Shi. Smart Contract Execution - the (+-)-Biased Ballot Problem. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 21:1-21:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ISAAC.2017.21,
  author =	{Chen, Lin and Xu, Lei and Gao, Zhimin and Shah, Nolan and Lu, Yang and Shi, Weidong},
  title =	{{Smart Contract Execution - the (+-)-Biased Ballot Problem}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{21:1--21:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.21},
  URN =		{urn:nbn:de:0030-drops-82388},
  doi =		{10.4230/LIPIcs.ISAAC.2017.21},
  annote =	{Keywords: Blockchain, Probability, Random Walk, Smart Contract}
}
Document
Defining and Evaluating Learner Experience for Social Adaptive E-Learning

Authors: Lei Shi

Published in: OASIcs, Volume 43, 2014 Imperial College Computing Student Workshop


Abstract
Social adaptive e-learning combines, threads and balances the amount of social and adaptive features for e-learning in order to achieve high-quality Learner eXperience (LX). Evaluating a social adaptive e-learning system is a difficult task due to its complexity. It is crucial to ensure that appropriate evaluation methods and measures are used. A User-centric approach serves the empirical system evaluation using subjective user feedback on satisfaction and productivity as well as the quality of work and support, so as to verify the quality of product, detect problems, and support decisions. This paper proposes a learner-centric evaluation framework, which applies a user-centric approach, aiming to evaluate LX in social adaptive e-learning from the end-user (learner) point of view, taking into consideration both social and adaptive perspectives.

Cite as

Lei Shi. Defining and Evaluating Learner Experience for Social Adaptive E-Learning. In 2014 Imperial College Computing Student Workshop. Open Access Series in Informatics (OASIcs), Volume 43, pp. 74-82, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{shi:OASIcs.ICCSW.2014.74,
  author =	{Shi, Lei},
  title =	{{Defining and Evaluating Learner Experience for Social Adaptive E-Learning}},
  booktitle =	{2014 Imperial College Computing Student Workshop},
  pages =	{74--82},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-76-7},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{43},
  editor =	{Neykova, Rumyana and Ng, Nicholas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ICCSW.2014.74},
  URN =		{urn:nbn:de:0030-drops-47765},
  doi =		{10.4230/OASIcs.ICCSW.2014.74},
  annote =	{Keywords: Social adaptive e-learning, user-centric evaluation, learner experience}
}
Document
Evaluation of Social Personalized Adaptive E-Learning Environments: End-User Point of View

Authors: Lei Shi, Malik Shahzad Awan, and Alexandra I. Cristea

Published in: OASIcs, Volume 35, 2013 Imperial College Computing Student Workshop


Abstract
The use of adaptations, along with the social affordances of collaboration and networking, carries a great potential for improving e-learning experiences. However, the review of the previous work indicates current e-learning systems have only marginally explored the integration of social features and adaptation techniques. The overall aim of this research, therefore, is to address this gap by evaluating a system developed to foster social personalized adaptive e-learning experiences. We have developed our first prototype system, Topolor, based on the concepts of Adaptive Educational Hypermedia and Social E-Learning. We have also conducted an experimental case study for the evaluation of the prototype system from different perspectives. The results show a considerably high satisfaction of the end users. This paper reports the evaluation results from end user point of view, and generalizes our method to a component-based evaluation framework.

Cite as

Lei Shi, Malik Shahzad Awan, and Alexandra I. Cristea. Evaluation of Social Personalized Adaptive E-Learning Environments: End-User Point of View. In 2013 Imperial College Computing Student Workshop. Open Access Series in Informatics (OASIcs), Volume 35, pp. 103-110, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@InProceedings{shi_et_al:OASIcs.ICCSW.2013.103,
  author =	{Shi, Lei and Awan, Malik Shahzad and Cristea, Alexandra I.},
  title =	{{Evaluation of Social Personalized Adaptive E-Learning Environments: End-User Point of View}},
  booktitle =	{2013 Imperial College Computing Student Workshop},
  pages =	{103--110},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-63-7},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{35},
  editor =	{Jones, Andrew V. and Ng, Nicholas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ICCSW.2013.103},
  URN =		{urn:nbn:de:0030-drops-42789},
  doi =		{10.4230/OASIcs.ICCSW.2013.103},
  annote =	{Keywords: adaptive educational hypermedia, social e-learning, evaluation}
}
Document
Apply the We!Design Methodology in E-learning 2.0 System Design: A Pilot Study

Authors: Lei Shi, Dana Al Qudah, and Alexandra I. Cristea

Published in: OASIcs, Volume 28, 2012 Imperial College Computing Student Workshop


Abstract
During the emergence of Web 2.0, the methodologies and technologies of E-learning have developed to a new era, E-learning 2.0, emphasises on social learning and the use of social interaction tools. The students are the main end-user of the E-learning 2.0 systems, so it is essential to take students' opinions into consideration during the design process of such systems. The We!Design participatory design methodology is proposed for incorporating undergraduate students in the development of educational systems. This pilot study aims to investigate how the We!Design methodology would work and what the results might propose, and gather initial preferences and improve the quality and efficiency of the larger scale studies in the future.

Cite as

Lei Shi, Dana Al Qudah, and Alexandra I. Cristea. Apply the We!Design Methodology in E-learning 2.0 System Design: A Pilot Study. In 2012 Imperial College Computing Student Workshop. Open Access Series in Informatics (OASIcs), Volume 28, pp. 123-128, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)


Copy BibTex To Clipboard

@InProceedings{shi_et_al:OASIcs.ICCSW.2012.123,
  author =	{Shi, Lei and Al Qudah, Dana and Cristea, Alexandra I.},
  title =	{{Apply the We!Design Methodology in E-learning 2.0 System Design: A Pilot Study}},
  booktitle =	{2012 Imperial College Computing Student Workshop},
  pages =	{123--128},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-48-4},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{28},
  editor =	{Jones, Andrew V.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ICCSW.2012.123},
  URN =		{urn:nbn:de:0030-drops-37750},
  doi =		{10.4230/OASIcs.ICCSW.2012.123},
  annote =	{Keywords: Participatory design, Requirement analysis, E-learning 2.0, Web 2.0}
}
  • Refine by Author
  • 3 Shi, Lei
  • 2 Chen, Lin
  • 2 Cristea, Alexandra I.
  • 2 Shi, Weidong
  • 2 Xu, Lei
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorial algorithms
  • 1 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 1 Blockchain
  • 1 E-learning 2.0
  • 1 Fixed parameter tractable
  • 1 Graver basis
  • 1 Integer Programming
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 1 2012
  • 1 2013
  • 1 2014
  • 1 2017
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail