学生面试问题

讨论了为学生面试安排老师的问题,通过合理的假设和简化,利用组合数学中的区组规划建立了数学模型,并采用了计算机模拟实现.最后,构造了优化的目标函数,并结合实际情况提出了一些为保证面试公平性应予以考虑的因素.     

学生面试问题的分配策略

就学生面试问题中的教师分配策略进行了系统的分析.首先我们分别给出并证明了在面试老师数一定,满足没有两个老师相同以及三个老师相同情形下的,可承担面试学生数的四个上界.然后提出了2种分配算法:排队算法和集合压缩算法,计算结果表明,所提算法可以很好的逼近理论上界.针对文理各半的情形,我们也同样提出并证明了类似的上界,两种分配策略同样适合文理各半的情形.在不分文理和文理各半的两种情况下,我们提出的分配策略都能很好的逼进甚至达到上界,同时也说明了我们理论界是一个很紧的上界.     

一个组面试问题的最佳顺序安排

采用边界阶段方法讨论最优组面试问题的最佳划分选择策略,在允许调整面试顺序的情况下,得到最优组面试问题中如何重新安排面试顺序能够以最大概率录用到最优应聘者的排序策略.     

一个不等式的证明

文[1]中提出了下述的不等式,即（符号说明见正文）AP＋PQ＋QB≤max{AP PQ′ Q′B,AP′ P′Q QB}。文中说：不难验证此不等式成立,但我们发现,要对此不等式给出一个详细的证明是相当困难的。由于此不等式对该文是相当重要的,本文即对之给出一个详细的证明。     

最优或次优组面试问题的最佳划分选择策略

本文研究了以选择绝对名次第一或第二的应聘者为目标的组面试问题的最佳停止规则,利用后退归纳法和边界阶段方法,获得最佳划分选择策略及确定两个边界阶段的最优不等式.     

堆取料机调度问题的一个近似算法

研究源自煤炭港口料场管理的堆取料机调度问题.该问题中,堆取料机从长为L的料场作业区最左端开始空机或载料运行,两者的速度之比为s：1（s ≥ 1）.决策者需确定储料堆在作业区的分布以及堆取料机处理它们的先后次序,目的是极小化一批煤料运输船的在港服务时间.考虑堆取料机处理完毕需要回到料场终端的作业模型,证明了存在最坏情况界不超过1+1/4s的近似算法.     

关于五个点的Steiner比猜想的一个简单的证明

Ｓｔｅｉｎｅｒ比猜想对任何正整数ｎ成立与否仍待解决，只有ｎ≤５的证明成立，ｎ＝５时有的证明过于繁琐或残缺。本文仍用伸与缩的方法，对ｎ＝５时给出一个真正简单的证明。     

一个组合问题的解法

问题在某次数学测验中,学号为i(i=1,2,3,4)的四位同学的考试成绩f(i)∈{85,89,90,91,95,99},且满足f(1)≤f(2)≤f(3)≤f(4),则这四位同学的考试成绩的所有可能情况的种数为()A.15种B.112种C.126种D.132种此类问题常见于高三的复习资料中,一般同学解这个问题多用分类讨论法,即讨     

抽象函数问题及其解法

抽象函数问题经常出现在高考试题中,且近几年有增多的趋势．由于抽象函数一般没给出具体解析式,高中学生往往有畏惧心理．在高考复习时,教师给予适当的指导是必要的．本文选取一些高考或复习题中出现的抽象函数问题,分类例举,以供参考．     

最小权点覆盖问题的一个近似算法

在点、边赋权的简单图中,关于最小权点覆盖问题,以经典的最短路算法-Dijkstra算法为基础,提出了一个求解该问题的近似算法.首先,在给定的赋权图中任选一点作为初始点,并给出允许集及相关定义.然后,利用经典的最短路算法-Dijkstra算法,求出初始点到允许集中各顶点的最短路径,并按照一定的原则选择近似最小权点覆盖集.最后,通过算例阐释了算法的实现过程的合理性及有效性.     

An Algorithmic Framework for the Exact Solution of the Prize-Collecting Steiner Tree Problem

The Prize-Collecting Steiner Tree Problem (PCST) on a graph with edge costs and vertex profits asks for a subtree minimizing the sum of the total cost of all edges in the subtree plus the total profit of all vertices not contained in the subtree. PCST appears frequently in the design of utility networks where profit generating customers and the network connecting them have to be chosen in the most profitable way. Our main contribution is the formulation and implementation of a branch-and-cut algorithm based on a directed graph model where we combine several state-of-the-art methods previously used for the Steiner tree problem. Our method outperforms the previously published results on the standard benchmark set of problems. We can solve all benchmark instances from the literature to optimality, including some of them for which the optimum was not known. Compared to a recent algorithm by Lucena and Resende, our new method is faster by more than two orders of magnitude. We also introduce a new class of more challenging instances and present computational results for them. Finally, for a set of large-scale real-world instances arising in the design of fiber optic networks, we also obtain optimal solution values. Received: April, 2004 This work has been partly supported by the RTNADONET, 504438, by the Doctoral Scholarship Program of the Austrian Academy of Sciences (DOC) and by CNR and MIUR, Italy.A preliminary version of this paper appeared as [21].     

On reductions for the Steiner Problem in Graphs

Several authors have demonstrated how reductions can be used to improve the efficiency with which the Steiner Problem in Graphs can be solved. Previous reduction algorithms have been largely ad hoc in nature. This paper uses a theory of confluence to show that, in many cases, all maximal reduction sequences are equivalent, gaining insights into the design of reduction algorithms that obtain a maximum degree of reduction.     

A distributed dual ascent algorithm for the Hop-constrained Steiner Tree Problem

The Hop-constrained Steiner Tree Problem is often used to model applications of multicast routing with QoS requirements. This paper introduces a distributed heuristic for the problem based on the application of dual ascent over a graph transformation introduced by Gouveia et al. The proposed algorithm is shown to yield significantly better solutions than the previously known algorithms.     

The Fine Intersection Problem for Steiner Triple Systems

The intersection of two Steiner triple systems and is the set . The fine intersection problem for Steiner triple systems is to determine for each v, the set I(v), consisting of all possible pairs (m, n) such that there exist two Steiner triple systems of order v whose intersection satisfies and . We show that for v ≡ 1 or 3 (mod 6), |I(v)| = Θ(v ³), where previous results only imply that |I(v)| = Ω(v ²). Received: January 23, 2006. Final Version received: September 2, 2006     

Two Heuristics for the Euclidean Steiner Tree Problem

The Euclidean Steiner tree problem is to find the tree with minimal Euclidean length spanning a set of fixed points in the plane, allowing the addition of auxiliary points to the set (Steiner points). The problem is NP-hard, so polynomial-time heuristics are desired. We present two such heuristics, both of which utilize an efficient method for computing a locally optimal tree with a given topology. The first systematically inserts Steiner points between edges of the minimal spanning tree meeting at angles less than 120 degrees, performing a local optimization at the end. The second begins by finding the Steiner tree for three of the fixed points. Then, at each iteration, it introduces a new fixed point to the tree, connecting it to each possible edge by inserting a Steiner point, and minimizes over all connections, performing a local optimization for each. We present a variety of test cases that demonstrate the strengths and weaknesses of both algorithms. This revised version was published online in July 2006 with corrections to the Cover Date.     

Polynomial Time Approximation Scheme for Symmetric Rectilinear Steiner Arborescence Problem

The Symmetric Rectilinear Steiner Arborescence (SRStA) problem is defined as follows: given a set of terminals in the positive quadrant of the plane, connect them using horizontal and vertical lines such that each terminal can be reached from the origin via a y-monotone path and the total length of all the line segments is the minimum possible. Finding an SRStA has applications in VLSI design, in data structures used in some optimization algorithms and in dynamic server problems. In this paper, we provide a polynomial time approximation scheme for the SRStA problem, improving the previous best approximation ratio of 3 for this problem.     

关于Evans问题的一类新解

给出判定Evans问题有解的一个充分条件,由此构造出一类新的Evans三角形,其三边长分别为8k5-8k3＋k＋1,8k5-8k3＋k-1和2k,三角形中最短边上的高与该边长之比是2（k2-1）（2k2-1）,这里k是大于1的正整数.     

Stability for the Dirichlet Problem under Continuous Steiner Symmetrization

In this paper we prove the existence of a deformation transforming an arbitrary open set into the ball, which has the following properties: it keeps constant the measure, the kth eigenvalue of Laplace–Dirichlet operator is continuous from the left and the first eigenvalue is decreasing. The deformation is given by a sequence of continuous Steiner symmetrizations, and the behavior of the eigenvalues is related to the stability of the Dirichlet problem.     

A Polynomial Time Approximation Scheme for the Grade of Service Steiner Minimum Tree Problem

In this paper, we present the design of a Polynomial Time Approximation Scheme (PTAS) for the Grade of Service Steiner Minimum Tree (GOSST) problem, which is known to be NP-Complete. Previous research has focused on geometric analyses and different approximation algorithms have been designed. We propose a PTAS that provides a polynomial time, near-optimal solution with performance ratio 1+. The GOSST problem has some important applications. In network design, a fundamental issue for the physical construction of a network structure is the interconnection of many communication sites with the best choice of the connecting lines and the best allocation of the transmission capacities over these lines. Good solutions should provide paths with enough communication capacities between any two sites, with the least network construction costs. Also, the GOSST problem has applications in transportation, for road constructions and some potential uses in CAD in terms of interconnecting the elements on a plane to provide enough flux between any two elements.