平面上的点-线选址问题

本文研究两类平面选址问题：（1）求一直线到n个给定点的加权距离和为最小；（2）求一点到n条给定直线的加权距离和为最小，对这两个非线性最优化问题，欠给出迭代次数为多项式的算法。     

关于Heilbron型问题的一个猜测

在数学竞赛中曾多次出现如下的Heilbron型问题:“设平面上任给n个点,每两点之间有一个距离,最大距离与最小距离的比记为又λ_n,求λ_n的最小值(下确界)”。人们已经知道λ_4≥2~(1/2),λ_5≥2sin3π╱10,λ_8≥3~(1/2)。当n≥7时,目前还没有任何结果,只是猜测λ_n≥2sin(n-2)╱(2n)π(见[1])。本文将给出这     

关于Heilbron型问题的一个猜测的纠正和证明

Heilbron型问题是组合几何中较为困难的问题,其中一个是: 平面上任给n个点,每两点之间有一个距离,最大距离与最小距离的比记为λ_n,求λ_n的     

一个具有两类工件的多目标排序的多项式时间算法

本文考虑具有两个工件集的单机排序问题.第一个工件集J1以完工时间和为目标函数,第二个工件集J2以最大加权完工时间为目标函数.问题的目标是寻找一种排序,使得两个目标函数的加权和达到最小.本文证明该问题可在O(n1n2(n1 n2))时间内求解.     

最小最大二点集覆盖问题分析及改进算法设计

本文考虑二中心问题的扩展问题-最小最大二点集覆盖问题。给定两个平面点集P₁和P₂,分别包含m和n个点,求两个圆分别覆盖P₁和P₂,并且要求两圆半径与两圆圆心距三者中的最大值最小。本文主要贡献在于分析半径变化过程中两个点集中心包之间最近距离的变化关系,其中中心包是点集所具有的一个特殊几何结构,所得到的结果改进了Huang等人之前给出的结果,并且通过该结果设计相应算法,所得到的算法复杂性是目前最好的。     

图的支撑树伸展与层叠最优化

在图的支撑树最优化中,有两个重要的优化指标:伸展度和层叠度.由此提出两个组合最优化问题:最小伸展支撑树问题,求一个图的支撑树,使得当所有边嵌入到此支撑树时,这些边的最大伸展距离为最小;最小层叠支撑树问题,求一个图的支撑树,使得当所有边嵌入到此支撑树时,每条树边上的最大重叠边数为最小.这两个问题确定出两个图论参数:树展和树层.本文主要论述树展和树层的基本结构性质,包括圈与余圈的对偶性、极值性、上下界、最优性刻画和最优值计算等.     

数列通项最值问题的流行解法——是错解吗？

已知数列{αn}，求αn的最大值或最小值，这是在解决数列问题时常常遇到的问题，其流行解法是：要使αn最大，则应满足{αn≥αn-1,αn≥αn＋1,其中n≥2．同样，要使αn最小，则应满足{αn≤αn-1，αn≤αn＋1，其中n≥2.     

关于正整数的立方部分

对于任意正整数n，定义u(n)为不大于n的最大立方数，v(n)为不小于n的最小立方数．研究了数列{u(n))和{v(n)}的性质，并给出了两个有趣的渐近公式．     

对一个“完全平方数的个数”问题的再探求

问题已知n为自然数,28 212 2n是一个完全平方数,求n．这是2002年《中学生数学》第9期(下) P36初二年级“课外练习”题2．在第10期(下)P39的“上期课外练习题解答”中给出了n的三个值．笔者用“凑”完全平方数的方法,又“找”到了n的两个值．也就是说,在这个问题     

加权斯坦勒尔问题

加权斯坦勒尔问题贝清泉（汕头大学数学系５１５０６３）平面上有三城市Ａ、Ｂ、Ｃ，求点Ｐ的位置以设立公共机场，要使三城市通向机场的公路网之长为极小．这样一个问题导致下述费马问题或称斯坦勒尔问题；即求ΔＡＢＣ所在平面上一点Ｐ，使Ｐ到三顶点距离之和：ＰＡ＋Ｐ...     

一类网络上的干线选址

考虑一类在网络上点到路的距离意义下的最优干线选址问题,这是一类新型的选址问题.首先证明所讨论的两个问题是NP-hard,然后讨论树的情况,给出了当G是树时求解问题的算法,该算法的复杂性是O(n2).并对一些特殊网络的情况进行了讨论.     

干线网络的选址问题研究

考虑平面上和三维空间中同时确定多条干线的干线网络选址问题.对于平面上情形,通过最小化每个点到离它最近干线的加权距离之和,给出了一种有限步终止算法和基于k-means聚类分析、加权全最小一乘和重抽样方法的线性类算法;对于空间情形,给出了线性聚类算法.通过计算机仿真说明以上算法可以有效地确定平面和空间中干线网络位置.     

Exact pseudopolynomial algorithms for a balanced 2-clustering problem

We consider the strongly NP-hard problem of partitioning a set of Euclidean points into two clusters so as to minimize the sum (over both clusters) of the weighted sum of the squared intracluster distances from the elements of the clusters to their centers. The weights of sums are the sizes of the clusters. The center of one cluster is given as input, while the center of the other cluster is unknown and determined as the average value over all points in the cluster (as the geometric center). Two variants of the problems are analyzed in which the cluster sizes are either given or unknown. We present and prove some exact pseudopolynomial algorithms in the case of integer components of the input points and fixed space dimension.     

Complexity of single machine scheduling subject to nonnegative inventory constraints

This paper focuses on single machine scheduling subject to inventory constraints. Jobs either add items to an inventory or remove items from that inventory. Jobs that have to remove items cannot be processed if the required number of items is not available. We consider scheduling problems on a single machine with the minimization of the total weighted completion time, the maximum lateness, and the number of tardy jobs, respectively, as objective and determine their computational complexity. Since the general versions of our problems turn out to be strongly NP-hard, we consider special cases by assuming that different jobs have certain parameter values in common. We determine the computational complexity for all special cases when the objective is either to minimize total completion time or to minimize maximum lateness and for several special cases when the objective is either to minimize total weighted completion time or to minimize the number of tardy jobs.     

Path problems in generalized stars, complete graphs, and brick wall graphs

Path problems such as the maximum edge-disjoint paths problem, the path coloring problem, and the maximum path coloring problem are relevant for resource allocation in communication networks, in particular all-optical networks. In this paper, it is shown that maximum path coloring can be solved optimally in polynomial time for bidirected generalized stars, even in the weighted case. Furthermore, the maximum edge-disjoint paths problem is proved NP-hard for complete graphs (undirected or bidirected), a constant-factor off-line approximation algorithm is presented for the weighted case, and an on-line algorithm with constant competitive ratio is given for the unweighted case. Finally, an open problem concerning the existence of routings that simultaneously minimize the maximum load and the number of colors is solved: an example for a graph and a set of requests is given such that any routing that minimizes the maximum load requires strictly more colors for path coloring than a routing that minimizes the number of colors.     

Single-machine and two-machine flowshop scheduling problems with truncated position-based learning functions

Scheduling with learning effects has received growing attention nowadays. A well-known learning model is called ‘position-based learning’ in which the actual processing time of a job is a non-increasing function of its position to be processed. However, the actual processing time of a given job drops to zero precipitously as the number of jobs increases. Motivated by this observation, we propose two truncated learning models in single-machine scheduling problems and two-machine flowshop scheduling problems with ordered job processing times, respectively, where the actual processing time of a job is a function of its position and a control parameter. Under the proposed learning models, we show that some scheduling problems can be solved in polynomial time. In addition, we further analyse the worst-case error bounds for the problems to minimize the total weighted completion time, discounted total weighted completion time and maximum lateness.     

Two Characterizations of Smooth Norms

In an arbitrary Minkowski space M, n2, let there be given an arbitrary finite set P of weighted points whose affine hull is n-dimensional. We show that the unit ball B of M has smooth boundary if and only if each median hyperplane (minimizing the sum of weighted distances with respect to P) is spanned by n affinely independent points from P. Moreover, B has the same property if and only if every center hyperplane (minimizing the maximal weighted distance with respect to P) has the same maximal distance to at least n+1 affinely independent points from P.     

A computational study and survey of methods for the single-row facility layout problem

The single-row facility layout problem (SRFLP) is an NP-hard combinatorial optimization problem that is concerned with the arrangement of n departments of given lengths on a line so as to minimize the weighted sum of the distances between department pairs. (SRFLP) is the one-dimensional version of the facility layout problem that seeks to arrange rectangular departments so as to minimize the overall interaction cost. This paper compares the different modelling approaches for (SRFLP) and applies a recent SDP approach for general quadratic ordering problems from Hungerländer and Rendl to (SRFLP). In particular, we report optimal solutions for several (SRFLP) instances from the literature with up to 42 departments that remained unsolved so far. Secondly we significantly reduce the best known gaps and running times for large instances with up to 110 departments.