2 Search Results for "He, Xin"


Document
Compact Visibility Representation of Plane Graphs

Authors: Jiun-Jie Wang and Xin He

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)


Abstract
The visibility representation (VR for short) is a classical representation of plane graphs. It has various applications and has been extensively studied. A main focus of the study is to minimize the size of the VR. It is known that there exists a plane graph $G$ with $n$ vertices where any VR of $G$ requires a grid of size at least (2/3)n x((4/3)n-3) (width x height). For upper bounds, it is known that every plane graph has a VR with grid size at most (2/3)n x (2n-5), and a VR with grid size at most (n-1) x (4/3)n. It has been an open problem to find a VR with both height and width simultaneously bounded away from the trivial upper bounds (namely with size at most c_h n x c_w n with c_h < 1 and c_w < 2$). In this paper, we provide the first VR construction with this property. We prove that every plane graph of n vertices has a VR with height <= max{23/24 n + 2 Ceil(sqrt(n))+4, 11/12 n + 13} and width <= 23/12 n. The area (height x width) of our VR is larger than the area of some of previous results. However, bounding one dimension of the VR only requires finding a good st-orientation or a good dual s^*t^*-orientation of G. On the other hand, to bound both dimensions of VR simultaneously, one must find a good $st$-orientation and a good dual s^*t^*-orientation at the same time, and thus is far more challenging. Since st-orientation is a very useful concept in other applications, this result may be of independent interests.

Cite as

Jiun-Jie Wang and Xin He. Compact Visibility Representation of Plane Graphs. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 141-152, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.STACS.2011.141,
  author =	{Wang, Jiun-Jie and He, Xin},
  title =	{{Compact Visibility Representation of Plane Graphs}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{141--152},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.141},
  URN =		{urn:nbn:de:0030-drops-30064},
  doi =		{10.4230/LIPIcs.STACS.2011.141},
  annote =	{Keywords: plane graph, plane triangulation, visibility representation, st-orientation}
}
Document
A Comparison of GAs Penalizing Infeasible Solutions and Repairing Infeasible Solutions on the 0-1 Knapsack Problem

Authors: Jun He, Yuren Zhou, and Xin Yao

Published in: Dagstuhl Seminar Proceedings, Volume 8051, Theory of Evolutionary Algorithms (2008)


Abstract
Constraints exist in almost every optimization problem. Different constraint handling techniques have been incorporated with genetic algorithms (GAs), however most of current studies are based on computer experiments. An example is Michalewicz's comparison among GAs using different constraint handling techniques on the 0-1 knapsack problem. The following phenomena are observed in experiments: 1) the penalty method needs more generations to find a feasible solution to the restrictive capacity knapsack than the repair method; 2) the penalty method can find better solutions to the average capacity knapsack. Such observations need a theoretical explanation. This paper aims at providing a theoretical analysis of Michalewicz's experiments. The main result of the paper is that GAs using the repair method are more efficient than GAs using the penalty method on both restrictive capacity and average capacity knapsack problems. This result of the average capacity is a little different from Michalewicz's experimental results. So a supplemental experiment is implemented to support the theoretical claim. The results confirm the general principle pointed out by Coello: a better constraint-handling approach should tend to exploit specific domain knowledge.

Cite as

Jun He, Yuren Zhou, and Xin Yao. A Comparison of GAs Penalizing Infeasible Solutions and Repairing Infeasible Solutions on the 0-1 Knapsack Problem. In Theory of Evolutionary Algorithms. Dagstuhl Seminar Proceedings, Volume 8051, pp. 1-39, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{he_et_al:DagSemProc.08051.3,
  author =	{He, Jun and Zhou, Yuren and Yao, Xin},
  title =	{{A Comparison of GAs Penalizing Infeasible Solutions and Repairing Infeasible Solutions on the 0-1 Knapsack Problem}},
  booktitle =	{Theory of Evolutionary Algorithms},
  pages =	{1--39},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8051},
  editor =	{Dirk V. Arnold and Anne Auger and Jonathan E. Rowe and Carsten Witt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08051.3},
  URN =		{urn:nbn:de:0030-drops-14822},
  doi =		{10.4230/DagSemProc.08051.3},
  annote =	{Keywords: Genetic Algorithms, Constrained Optimization, Knapsack Problem, Computation Time, Performance Analysis}
}
  • Refine by Author
  • 1 He, Jun
  • 1 He, Xin
  • 1 Wang, Jiun-Jie
  • 1 Yao, Xin
  • 1 Zhou, Yuren

  • Refine by Classification

  • Refine by Keyword
  • 1 Computation Time
  • 1 Constrained Optimization
  • 1 Genetic Algorithms
  • 1 Knapsack Problem
  • 1 Performance Analysis
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2008
  • 1 2011

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