Worm Problem的一个新上界

1966年,Leo Moser提出了一个基本的几何问题,即Worm Problem．该问题是指:在平面上寻找一个面积最小的(凸)区域,使得任何一条长为1的平面曲线都能够通过旋转和平移完全放入该(凸)区域之中．对于要寻找的区域是凸的情形,本文将把目前所知道的最小的上界由0．2738086降低至0．270911861．在最后一部分,我们推广了Worm Problem,并初步给出了一些相应的结果．     

Randomized Complexity Lower Bound for Arrangements and Polyhedra

The complexity lower bound Ω (log N ) for randomized computation trees is proved for recognizing an arrangement or a polyhedron with N faces. This provides, in particular, the randomized lower bound Ω (n log n ) for the DISTINCTNESS problem and generalizes [11] where the randomized lower bound Ω (n ² ) was ascertained for the KNAPSACK problem. The core of the method is an extension of the lower bound from [8] on the multiplicative complexity of a polynomial. Received May 14, 1997, and in revised form October 27, 1997, and February 16, 1998.     

An Improved Upper Bound for Leo Moser's Worm Problem

Abstract. A worm ω is a continuous rectifiable arc of unit length in the Cartesian plane. Let W denote the class of all worms. A planar region C is called a cover for W if it contains a copy of every worm in W . That is, C will cover or contain any member ω of W after an appropriate translation and/ or rotation of ω is completed (no reflections). The open problem of determining a cover C of smallest area is attributed to Leo Moser [7], [8]. This paper reduces the smallest known upper bound for this area from 0.275237 [10] to 0.260437.     

An Improved Upper Bound for Leo Moser's Worm Problem

   Abstract. A worm ω is a continuous rectifiable arc of unit length in the Cartesian plane. Let W denote the class of all worms. A planar region C is called a cover for W if it contains a copy of every worm in W . That is, C will cover or contain any member ω of W after an appropriate translation and/ or rotation of ω is completed (no reflections). The open problem of determining a cover C of smallest area is attributed to Leo Moser [7], [8]. This paper reduces the smallest known upper bound for this area from 0.275237 [10] to 0.260437.     

An Improved Lower Bound for the Multimedian Location Problem

We consider the problem of locating, on a network, n new facilities that interact with m existing facilities. In addition, pairs of new facilities interact. This problem, the multimedian location problem on a network, is known to be NP-hard. We give a new integer programming formulation of this problem, and show that its linear programming relaxation provides a lower bound that is superior to the bound provided by a previously published formulation. We also report results of computational testing with both formulations.     

An Improved Bound for \sl k -Sets in Three Dimensions

We prove that the maximum number of k -sets in a set S of n points in \Bbb R ³ is O(nk ^3/2 ) . This improves substantially the previous best known upper bound of O(nk ^5/3 ) (see [7] and [1]). Received November 30, 1999, and in revised form July 24, 2000. Online publication February 26, 2001.     

改进型Hardy-Sobolev不等式最好常数的一个上界

在本文,我们对改进型Hardy-Sobolev不等式的最好常数进行研究,得到该常数的一个上界.     

An Improved Branch & Bound Method for the Uncapacitated Competitive Location Problem

In this paper, the problem of locating new facilities in a competitive environment is considered. The problem is formulated as the firm expected profit maximization and a set of nodes is selected in a graph representing the geographical zone. Profit depends on fixed and deterministic location costs and, since customers are independent decision-makers, on the expected market share. The problem is an instance of nonlinear integer programming, because the objective function is concave and submodular. Due to this complexity a branch & bound method is developed for solving small size problems (that is, when the number of nodes is less than 50), while a heuristic is necessary for larger problems. The branch & bound is called data-correcting method, while the approximate solutions are obtained using the heuristic-concentration method.     

An Improved Bound on the Number of Unit Area Triangles

We show that the number of unit-area triangles determined by a set of n points in the plane is O(n ^9/4+ε ), for any ε>0, improving the recent bound O(n ^44/19) of Dumitrescu et al.     

The Space of Unordered Real Line Arrangements

The set of all unordered real line arrangements of given degree in the real projective plane is known to have a natural semialgebraic structure. The nonreduced arrangements are singular points of this structure. We show that the set of all unordered real line arrangements of given degree also has a natural structure of a smooth compact connected affine real algebraic variety. In fact, as such, it is isomorphic to a real projective space. As a consequence, we get a projectively linear structure on the set of all real line arrangements of given degree. We also show that the universal family of unordered real line arrangements of given degree is not algebraic.     

An Improved Bound on the One-Sided Minimum Crossing Number in Two-Layered Drawings

Given a bipartite graph G = (V,W,E), a two-layered drawing consists of placing nodes in the first node set V on a straight line L₁ and placing nodes in the second node set W on a parallel line L₂. The one-sided crossing minimization problem asks one to find an ordering of nodes in V to be placed on L₁ so that the number of arc crossings is minimized. In this paper we use a 1.4664-approximation algorithm for this problem. This improves the previously best bound 3 due to P. Eades and N. C. Wormald [Edge crossing in drawing bipartite graphs, Algorithmica 11 (1994), 379-403].     

An Indefinite Kahler Metric on the Space of Oriented Lines

The total space of the tangent bundle of a Kähler manifoldadmits a canonical Kähler structure. Parallel translationidentifies the space T of oriented affine lines in R³ with thetangent bundle of S². Thus the round metric on S² induces aKähler structure on T which turns out to have a metricof neutral signature. It is shown that the identity componentof the isometry group of this metric is isomorphic to the identitycomponent of the isometry group of the Euclidean metric on R³. The geodesics of this metric are either planes or helicoidsin R³. The signature of the metric induced on a surface inT is determined by the degree of twisting of the associatedline congruence in R³, and it is shown that, for Lagrangian,the metric is either Lorentz or totally null. For such surfacesit is proved that the Keller–Maslov index counts the numberof isolated complex points of J inside a closed curve on .     

An Improved Bound for Vertex Partitions by Connected Monochromatic K‐Regular Graphs

Improving a result of Sárközy and Selkow, we show that for all integers there exists a constant such that if and the edges of the complete graph are colored with r colors then the vertex set of can be partitioned into at most vertex disjoint connected monochromatic k‐regular subgraphs and vertices. This is close to best possible. © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 127–145, 2013     

An Improved Upper Complexity Bound for the Topology Computation of a Real Algebraic Plane Curve

The computation of the topological shape of a real algebraic plane curve is usually driven by the study of the behavior of the curve around its critical points (which includes also the singular points). In this paper we present a new algorithm computing the topological shape of a real algebraic plane curve whose complexity is better than the best algorithms known. This is due to the avoiding, through a sufficiently good change of coordinates, of real root computations on polynomials with coefficients in a simple real algebraic extension of to deal with the critical points of the considered curve. In fact, one of the main features of this algorithm is that its complexity is dominated by the characterization of the real roots of the discriminant of the polynomial defining the considered curve.     

An Improved Upper Bound on the Total Restrained Domination Number in Cubic Graphs

In this paper, we continue the study of total restrained domination in graphs. A set S of vertices in a graph G = (V, E) is a total restrained dominating set of G if every vertex of G is adjacent to some vertex in S and every vertex of ${V {\setminus} S}$ is adjacent to a vertex in ${V {\setminus} S}$ . The minimum cardinality of a total restrained dominating set of G is the total restrained domination number γ _tr(G) of G. Jiang et?al. (Graphs Combin 25:341–350, 2009) showed that if G is a connected cubic graph of order n, then γ _tr(G) ≤ 13n/19. In this paper we improve this upper bound to γ _tr(G) ≤ (n?+?4)/2. We provide two infinite families of connected cubic graphs G with γ _tr(G) = n/2, showing that our new improved bound is essentially best possible.     

An Elementary Example of an Order Bound Dual Space that is not Directed

This paper presents an elementary example of an order bounded linear functional on a directed partially ordered vector space that is not equal to the difference of two positive linear functionals.     

An Improved Upper Bound on the Linear 2-arboricity of 1-planar Graphs

The linear 2-arboricity la_2(G) of a graph G is the least integer k such that G can be partitioned into k edge-disjoint forests,whose component trees are paths of length at most 2.In this paper,we prove that if G is a 1-planar graph with maximum degree Δ,then la_2(G)≤[(Δ+1)/2]+7.This improves a known result of Liu et al.(2019) that every 1-planar graph G has la_2(G)≤[(Δ+1)/2]+14.We also observe that there exists a 7-regular 1-planar graph G such that la_2(G)=6=[(Δ+1)/2]+2,which implies that our solution is within 6 from optimal.     

An Upper Bound for List T-Colourings

Erds, Rubin and Taylor showed in 1979 that for any connectedgraph G which is not a complete graph or an odd cycle, ch(G) , where is the maximum degree of a vertex in G and ch(G) isthe choice number of the graph (also proved by Vizing in 1976).They also gave a characterisation of D-choosability. A graphG is D-choosable if, when we assign to each vertex v of G alist containing d(v) elements, where d(v) is the degree of vertexv, we can always choose a proper vertex colouring from theselists, however the lists were chosen. In this paper we shallgeneralise their results on the choice number of G and D-choosabilityto the case where we have T-colourings.