The mean field traveling salesman and related problems

The mean field traveling salesman and related problems: "

Abstract The edges of a complete graph on n vertices are assigned i.i.d. random costs from a distribution for which the interval [0, t] has probability asymptotic to t as t→0 through positive values. In this so called pseudo-dimension 1 mean field model, we study several optimization problems,
of which the traveling salesman is the best known. We prove that, as n→∞, the cost of the minimum traveling salesman tour converges in probability to a certain number, approximately 2.0415, which
is characterized analytically.

• Content Type Journal Article
• DOI 10.1007/s11511-010-0046-7
• Authors
  
  
  • Johan Wästlund, Chalmers University of Technology Department of Mathematical Sciences SE-412 96 Gothenburg Sweden
  
  

• Journal Acta Mathematica
• Online ISSN 1871-2509
• Print ISSN 0001-5962

"

Tiling Polygons with Lattice Triangles

Tiling Polygons with Lattice Triangles: "

Abstract Given a simple polygon with rational coordinates having one vertex at the origin and an adjacent vertex on the x-axis, we look at the problem of the location of the vertices for a tiling of the polygon using lattice triangles (i.e., triangles
which are congruent to a triangle with the coordinates of the vertices being integer). We show that the coordinates of the
vertices in any tiling are rationals with the possible denominators odd numbers dependent on the cotangents of the angles
in the triangles.

• Content Type Journal Article
• DOI 10.1007/s00454-010-9249-0
• Authors
  
  
  • Steve Butler, University of California, Los Angeles Los Angeles CA USA
  • Fan Chung, University of California, San Diego San Diego CA USA
  • Ron Graham, University of California, San Diego San Diego CA USA
  • Miklós Laczkovich, Eötvös Loránd University Budapest Hungary
  
  

• Journal Discrete and Computational Geometry
• Online ISSN 1432-0444
• Print ISSN 0179-5376

"

On Rich Lines in Grids

On Rich Lines in Grids: "

Abstract In this paper we show that if one has a grid A×B, where A and B are sets of n real numbers, then there can be only very few “rich” lines in certain quite small families. Indeed, we show that if the family
has lines taking on n

^ε
distinct slopes, and where each line is parallel to n

^ε
others (so, at least n
^2ε
lines in total), then at least one of these lines must fail to be “rich”. This result immediately implies non-trivial sumproduct
inequalities; though, our proof makes use of the Szemeredi-Trotter inequality, which Elekes used in his argument for lower
bounds on |C+C|+|C.C|.

• Content Type Journal Article
• DOI 10.1007/s00454-010-9250-7
• Authors
  
  
  • Evan Borenstein, Georgia Institute of Technology School of Mathematics 103 Skiles Atlanta GA 30332 USA
  • Ernie Croot, Georgia Institute of Technology School of Mathematics 103 Skiles Atlanta GA 30332 USA
  
  

• Journal Discrete and Computational Geometry
• Online ISSN 1432-0444
• Print ISSN 0179-5376

"

On Lines and Joints

On Lines and Joints: "

Abstract Let L be a set of n lines in ℝ
^d
, for d≥3. A joint of L is a point incident to at least d lines of L, not all in a common hyperplane. Using a very simple algebraic proof technique, we show that the maximum possible number
of joints of L is Θ(n

^d/(d−1)). For d=3, this is a considerable simplification of the original algebraic proof of Guth and Katz (Algebraic methods in discrete
analogs of the Kakeya problem, 4 December 2008, arXiv:0812.1043), and of the follow-up simpler proof of Elekes et al. (On lines, joints, and incidences in three dimensions. Manuscript,
11 May 2009, arXiv:0905.1583). Some extensions, e.g., to the case of joints of algebraic curves, are also presented.

• Content Type Journal Article
• DOI 10.1007/s00454-010-9246-3
• Authors
  
  
  • Haim Kaplan, Tel Aviv University School of Computer Science Tel Aviv 69978 Israel
  • Micha Sharir, Tel Aviv University School of Computer Science Tel Aviv 69978 Israel
  • Eugenii Shustin, Tel Aviv University School of Mathematical Sciences Tel Aviv 69978 Israel
  
  

• Journal Discrete and Computational Geometry
• Online ISSN 1432-0444
• Print ISSN 0179-5376

"

Generalized Jacobi Rational Spectral Method and Its Applications

Generalized Jacobi Rational Spectral Method and Its Applications: "

Abstract We introduce an orthogonal system on the whole line, induced by the generalized Jacobi functions. Some results on the generalized
Jacobi rational approximation are established, which play important roles in the related spectral methods. As examples of
applications, the rational spectral schemes are proposed for sine-Gordon, Klein-Gordon and Fisher equations, with the convergence
analysis. Numerical results demonstrate their efficiency.

• Content Type Journal Article
• DOI 10.1007/s10915-010-9353-6
• Authors
  
  
  • Ben-Yu Guo, Shanghai Normal University, Scientific Computing Key Laboratory of Shanghai Universities, Division of Computational Science of E-institute of Shanghai Universities Department of Mathematics Shanghai 200234 China
  • Yong-Gang Yi, Tianhua College Department of Basic Courses Shanghai 201805 China
  
  

• Journal Journal of Scientific Computing
• Online ISSN 1573-7691
• Print ISSN 0885-7474

"