On the Complexity of Matroid Isomorphism Problem

We study the complexity of testing if two given matroids are isomorphic. The problem is easily seen to be in S₂^p\Sigma_{2}^{p}. In the case of linear matroids, which are represented over polynomially growing fields, we note that the problem is unlikely to be S₂^p\Sigma_{2}^{p}-complete and is co NP-hard. We show that when the rank of the matroid is bounded by a constant, linear matroid isomorphism, and matroid isomorphism are both polynomial time many-one equivalent to graph isomorphism.     

The Simulated Greedy Algorithm for Several Submodular Matroid Secretary Problems

We study the matroid secretary problems with submodular valuation functions. In these problems, the elements arrive in random order. When one element arrives, we have to make an immediate and irrevocable decision on whether to accept it or not. The set of accepted elements must form an independent set in a predefined matroid. Our objective is to maximize the value of the accepted elements. In this paper, we focus on the case that the valuation function is a non-negative and monotonically non-decreasing submodular function. We introduce a general algorithm for such submodular matroid secretary problems. In particular, we obtain constant competitive algorithms for the cases of laminar matroids and transversal matroids. Our algorithms can be further applied to any independent set system defined by the intersection of a constant number of laminar matroids, while still achieving constant competitive ratios. Notice that laminar matroids generalize uniform matroids and partition matroids. On the other hand, when the underlying valuation function is linear, our algorithm achieves a competitive ratio of 9.6 for laminar matroids, which significantly improves the previous result.     

秘书问题中聘用双方策略研究

秘书问题是一类概率最优化问题,鉴于现实应用中其理论最优策略缺乏可操作性,而传统启发式策略仅关注阀值确定,不涉及阀值和标杆关系的定量分析。为此,推导“截止阀法则”中阀值与标杆的最优组合关系,提出一种“三分决策法”聘用策略,以总量的1/3为样本,并以1号~3号标杆为参照选取目标,运用多主体系统的建模方法,对应聘策略进行分等级讨论,分析2种不同竞争模式下,优劣各异的应聘者在应聘队列中最大化录用概率。应用结果表明,该策略简便易行,且有效性能达到最优理论解性能的95%以上。     

顶点覆盖变体问题的确定参数可解算法研究

参数复杂性作为算法研究的一个重要分支,近十年来在国际上受到了广泛的关注,确定参数可解算法是参数复杂性研究的一类重要问题,因此被广泛研究。本文主要研究了顶点覆盖问题的两个变体问题：一个是连接的顶点覆盖问题,二是含权的树型顶点覆盖问题。这两个问题都是对原始的顶点覆盖问题加入了一些限制的变体问题。本文给出了这两个问题的确定参数可解算法,并且是目前的最好结果。     

Benders Decomposition Algorithms for Two Variants of the Single Allocation Hub Location Problem

Networks and Spatial Economics - The hub location problem (HLP) is a special type of the facility location problem with numerous applications in the airline industry, postal services, and computer...     

On Independence of Variants of the Weak Pigeonhole Principle

The principle states that no oracle circuit can compute a surjection of a onto b. We showthat is independent of for various choices of the parameters, , , P. We also improve the known separation of iWPHP(PV) from under cryptographic assumptions.     

On the Information-Adaptive Variants of the ADMM: An Iteration Complexity Perspective

Designing algorithms for an optimization model often amounts to maintaining a balance between the degree of information to request from the model on the one hand, and the computational speed to expect on the other hand. Naturally, the more information is available, the faster one can expect the algorithm to converge. The popular algorithm of ADMM demands that objective function is easy to optimize once the coupled constraints are shifted to the objective with multipliers. However, in many applications this assumption does not hold; instead, often only some noisy estimations of the gradient of the objective—or even only the objective itself—are available. This paper aims to bridge this gap. We present a suite of variants of the ADMM, where the trade-offs between the required information on the objective and the computational complexity are explicitly given. The new variants allow the method to be applicable on a much broader class of problems where only noisy estimations of the gradient or the function values are accessible, yet the flexibility is achieved without sacrificing the computational complexity bounds.     

超文本中的迷路问题

迷路问题是用户在超文梧导航时面临的最大难题，本文分析了用户迷路的根本原因，阐述了当前解决迷路问题的主要方法，指出超文本的结构化，搜索／查询机制的使用和知识的利用是解决迷路问题的关键。     

认识“网络秘书”

本文探讨了社会信息化网络化发展进程中出现的新生事物网络秘书,通过对10余年发展历史考察和社会现状分析,认为网络秘书实际上可以分为三类,这就是软件型网络秘书、公司型网络秘书和职员型网络秘书,其中以网上助理或网上秘书为代表的职员型网络秘书,是网络秘书职业发展的核心和关键;同时认为目前社会对于网络秘书的认识还很模糊,需要加强研究和宣传,推动这一新生事物的健康发展。     

拟阵贪婪算法在景区装饰灯中的应用

该文立足于实际,就如何在景区设置装饰灯问题给出了数学模型及求解步骤。在解决过程中采用了拟阵的贪婪算法,此算法简洁、易行。     

拟阵贪婪算法在景区装饰灯中的应用

该文立足于实际，就如何在景区设置装饰灯问题给出了数学模型及求解步骤。在解决过程中采用了拟阵的贪婪算法，此算法简洁、易行。     

Algorithm of Sequential Analysis of Variants for Minimization of the Number of Devices in Scheduling Problem with Due Date

This paper deals with the problem where a set of n demands arrives at a system of M identical parallel devices. Each demand i is put on the queue for service at the moment of time d_i 0 and is serviced during t_i > 0 time units by any device without interruption. A directive period D_i is assigned to each demand i. An algorithm is proposed for construction of an optimal schedule (relative to the number of devices) which is based on the method of successive analysis of variants.     

MSP问题NP完全性研究

针对文献[1,2]提出的MSP问题,研究了MSP问题与着色问题、子图同构问题的对应关系,揭示了MSP问题所反映的NP完全问题的共性;分析了MSP问题的相变现象,为文献[1,2]提出的多项式时间算法框架的测试提供了难例产生方法。     

耶鲁枪击问题之分析

本文以耶鲁枪击问题为例,分析了典型的非单调理论在解决框架问题上的局限性;在综述了已有的解决方案所存在的问题后,指出了非单调的推理与逻辑程序设计系统GKD—NMRS在描述和解决框架问题上的简洁性和直观性。     

On the Input Problem for Massive Modularity

Jerry Fodor argues that the massive modularity thesis – the claim that (human) cognition is wholly served by domain specific, autonomous computational devices, i.e., modules – is a priori incoherent, self-defeating. The thesis suffers from what Fodor dubs the input problem: the function of a given module (proprietarily understood) in a wholly modular system presupposes non-modular processes. It will be argued that massive modularity suffers from no such a priori problem. Fodor, however, also offers what he describes as a really real input problem (i.e., an empirical one). It will be suggested that this problem is real enough, but it does not selectively strike down massive modularity – it is a problem for everyone.     

On k-Positive Satisfiability Problem

1IntroductionThesatisfiabilityproblem(SAT)isthedecisionproblemwhetheragivenpropositionalformulainconjunctivenormalform(CNF)couldbesatisfiedbyanyassignmenttotheatoms.ItiswellknownthatSATisNP-complete[1].SounderthehypothesisthatP/NP,thereisnopolynomialtimealgorithmforsolvingSAT121.Letk-SATbethesubproblemrestrictingtheclausesnotlongerthank.Thenk-SATisNP-completefork23['],andislineartimesolvablefork<213'4].Thefirstnontrivialupperboundontimecomplexityofk--SAT(k23)wasgivenin[5].Thereaki…     

On the Combined Problem of Compaction and Sorting

Under certain assumptions, a garbage collection algorithm which compacts the dynamic storage area also involves sorting a set of pointers, whose order usually has only been partially disturbed since the last garbage coliection. Using this structure and combining the sorting and compaction, we can achieve a rather important reduction of the time to perform a garbage collection.