| 学生面试问题的一个解法 |
| |
| 引用本文： | 夏立荣,陈建鑫,张晓彤.学生面试问题的一个解法[J].数学的实践与认识,2007,37(14):145-152. |
| |
| 作者姓名： | 夏立荣 陈建鑫 张晓彤 |
| |
| 作者单位： | 清华大学,计算机科学与技术系,北京,100084 |
| |
| 摘 要： | 研究的是自主招生的面试安排问题.它与一个经典问题(Steiner System问题)有很紧密的联系.首先我们形式化地提出了这个问题,并针对问题提出了3种算法.值得一提的是,我们提出的同余构造算法在时间复杂度较低的情况下,具有很高的近似比(强于FPTAS).对于文理分科的情况,我们同样在形式化地提出问题之后,给出了相应的算法.我们编写程序实现了所述的算法.
|
| 关 键 词： | 高考 面试 Steiner System 近似算法 |
| 修稿时间： | 2007年3月1日 |
A Solution for Student Interview Problem |
| |
| XIA Li-rong,CHEN Jian-xin,ZHANG Xiao-tong.A Solution for Student Interview Problem[J].Mathematics in Practice and Theory,2007,37(14):145-152. |
| |
| Authors: | XIA Li-rong CHEN Jian-xin ZHANG Xiao-tong |
| |
| Abstract: | We study the interview arrangement problem in autonomy enrollment,which has a tight relation with a classical model(Steiner System).We first introduce the problem formally.Then we propose three algorithms for the model.It deserves to be mentioned that the Modulo Construction algorithm we proposed has a sufficiently large approximation ratio with a low time complexity.We also provide corresponding algorithms for the condition of arts and science separateness.We implement all the algorithms mentioned in this paper. |
| |
| Keywords: | Steiner System |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
