Multicut问题参数算法的改进

Multicut问题即在一个图上删除最少个数的顶点,使得预先给定的一组顶点对均不连通.该问题是NP难的.在深入分析问题结构特点的基础上,运用集合划分策略和相关问题的最新研究结果,对它提出了一种时间复杂度为O*的参数化算法,其中,l为给定的顶点对数目,k为需删除的顶点个数.该算法明显改进了当前时间复杂度为O*的最好算法.     

树上推广的Multicut问题的近似算法

给定边上有费用的树T,终端集合族X={S\\-1,S\\-2,…,S\\-l},推广的Multicut问题询问费用最小的边集,使得在树上删除边集中的边能够断开每一个终端集.推广的Multicut问题有其独立的研究意义,因为该问题分别是经典的Multicut问题和Multiway Cut问题的自然推广,同时也是推广的Steiner Forest问题的对偶问题.树上推广的Multicut问题的完全版本可以归约到树上经典的Multicut问题近似求解.对于该问题的Prize-collecting版本,给出了原始对偶的3倍近似算法.对于该问题的k版本,通过非一致的途径给出了近似比为min{2（l-k+1）,k}的近似算法.以及找到了该问题的k版本与k-稠密子图问题之间的一个有趣的联系,从而证明了将k版本的树上推广的Multicut问题近似到O（n\\+\\{16-ε\\}）以内是困难的（对某个小的常数ε>0）.     

Multiway merging in parallel

The problem of merging k (k⩾2) sorted lists is considered. We give an optimal parallel algorithm which takes O((n log k/p)+log n) time using p processors on a parallel random access machine that allows concurrent reads and exclusive writes, where n is the total size of the input lists. This algorithm achieves O(log n) time using p=n log k/log n processors. Most of the previous log n research for this problem has been focused on the case when k=2. Very recently, parallel solutions for the case when k=2 have been reported. Our solution is the first logarithmic time optimal parallel algorithm for the problem when k⩾2. It can also be seen as a unified optimal parallel algorithm for sorting and merging. In order to support the algorithm, a new processor assignment strategy is also presented     

Multiway wideband power dividers

In this article, we propose a new design methodology to broaden the bandwidth of a multiway Bagley power divider (BPD). Single‐frequency matching uniform quarter‐wave‐length microstrip lines in the conventional design are replaced with impedance‐varying transmission lines of broadband matching characteristics. The equivalent transmission line model is used for profiling impedance variations, which are governed by a truncated Fourier series. Such variations are determined by finding the optimum series coefficients that result in a wideband matching nature. The proposed technique leads to flexible spectrum allocation and matching level. Furthermore, the resulting structures are compact and planar. First, analytical results of three 3‐way BPDs of different fractional bandwidths are presented and discussed to validate the proposed approach. Then, two examples of 3‐ and 5‐way BPDs with bandwidths of 4–10 GHz and 5–9 GHz, respectively, are simulated, fabricated, and measured. Simulated and measured results are in a good agreement, with input port matching of below ?15 dB and ?12.5 dB for the 3‐ and 5‐way dividers, respectively, over the bands of interest. The obtained transmission parameters of the 3‐ and 5‐way dividers are ?4.77 ± 1 dB and ?7 ± 1 dB, respectively, over the design bands. The proposed wideband dividers find many applications in microwave front‐end circuitry, especially in only‐transmitting antenna subsystems, such as broad‐ and multicast communication links. © 2015 Wiley Periodicals, Inc. Int J RF and Microwave CAE 25:730–738, 2015.     

Multicut问题参数算法的改进

Multicut问题即在一个图上删除最少个数的顶点,使得预先给定的一组顶点对均不连通.该问题是NP难的.在深入分析问题结构特点的基础上,运用集合划分策略和相关问题的最新研究结果,对它提出了一种时间复杂度为O*的参数化算法,其中,l为给定的顶点对数目,k为需删除的顶点个数.该算法明显改进了当前时间复杂度为O*的最好算法.     

Multiway tele-immersion at Supercomputing 97

Tele-immersion-the union of networked virtual reality (VR) and video to support collaboration among scientists, engineers, and educators-is an important element in the computing information infrastructure envisioned by the National Computational Science Alliance. Tele-immersion will let people from around the world casually enter a shared virtual environment (VE), manipulate that environment-whether a scientific simulation or a design space-and engage in discourse with their collaborators. The Alliance consists of more than 50 universities and government institutions led by the National Center for Supercomputing Applications. Supercomputing 97 provided an excellent opportunity to connect several of the Alliance partners together and experiment with the kind of shared interaction my colleagues and I will be focusing on in the next few years. Rather than show a tele-immersion demo at Supercomputing, we wanted to use the conference as an opportunity to do research on the show floor     

Strategic Conversations Under Imperfect Information: Epistemic Message Exchange Games

This paper refines the game theoretic analysis of conversations in Asher et al. (J Philos Logic 46:355–404, 2017) by adding epistemic concepts to make explicit the intuitive idea that conversationalists typically conceive of conversational strategies in a situation of imperfect information. This ‘epistemic’ turn has important ramifications for linguistic analysis, and we illustrate our approach with a detailed treatment of linguistic examples.     

Constraint-Based Processing of Multiway Spatial Joins

A multiway spatial join combines information found in three or more spatial relations with respect to some spatial predicates. Motivated by their close correspondence with constraint satisfaction problems (CSPs), we show how multiway spatial joins can be processed by systematic search algorithms traditionally used for CSPs. This paper describes two different strategies, window reduction and synchronous traversal, that take advantage of underlying spatial indexes to prune the search space effectively. In addition, we provide cost models and optimization methods that combine the two strategies to compute more efficient execution plans. Finally, we evaluate the efficiency of the proposed techniques and the accuracy of the cost models through extensive experimentation with several query and data combinations. Received December 21, 1998; revised September 29, 1998.     

一种基于Multiway cut的多对象图像分割*

多对象分割是图像处理中的一个难题,基于Multiway cut的图像分割是一种人工交互式多对象分割方法,能够实现图像的粗分割和精确分割。使用分水岭分割图像,把图像分割为属性相似的小区域;根据交互建立节点层次图,构建带权无向网络;不同层次的节点参与不同的运算,采用Multiway cut迭代分割;交互和分割可以多次执行,直至满足用户的要求。实验结果表明,该方法人工参与方便,准确度得到提高,速度满足现场操作的要求。     

纵横多路并行归并算法

基于倾斜与振荡法多路归并排序算法,提出了纵横多路并行归并算法,与已有方法递归应用两路归并过程不同.该算法直接对m×k的矩阵(m,k为任意整数)进行排序,消除了对两路递归过程的依赖,是一种新的多路归并排序算法.通过和倾斜与振荡法多路归并排序算法和高效的任意路并行归并算法的性能分析比较,当3k40时,该算法的时间复杂性低于同类算法.同时,该算法在专用硬件实现的设计复杂性上也具有明显的优势.     

Noninvasive BCIs: Multiway Signal-Processing Array Decompositions

In addition to helping better understand how the human brain works, the brain-computer interface neuroscience paradigm allows researchers to develop a new class of bioengineering control devices and robots, offering promise for rehabilitation and other medical applications as well as exploring possibilities for advanced human-computer interfaces.     

Multiway Decision Graphs for Automated Hardware Verification

Traditional ROBDD-based methods of automated verification suffer from the drawback that they require a binary representation of the circuit. To overcome this limitation we propose a broader class of decision graphs, called Multiway Decision Graphs (MDGs), of which ROBDDs are a special case. With MDGs, a data value is represented by a single variable of abstract type, rather than by 32 or 64 boolean variables, and a data operation is represented by an uninterpreted function symbol. MDGs are thus much more compact than ROBDDs, and this greatly increases the range of circuits that can be verified. We give algorithms for MDG manipulation, and for implicit state enumeration using MDGs. We have implemented an MDG package and provide experimental results.     

几类特殊图中的最小最大多路割

给定边具有正权的无向图,并指定若干个称为终端的顶点,最小最大多路割问题是要得到所有顶点的一个聚类,要求每个子类恰好包含一个终端,并使得所有子类的最大费用最小。子类的费用定义为该子类边界上所有边的权之和。最小最大多路割问题源于对等网络中的数据放置,是传统多路割问题的一个变形。当给定无向图是树图时,这一问题已经是强NP难解的。对于链图和环图,给出了线性时间的精确算法,该算法同时也使得所有子类的总费用最小。对于树图和限制树宽图,给出了(2-1/2k2)-近似算法,k表示终端的数目。     

A Syntactic Framework with Probabilistic Beliefs and Conditionals for the Analysis of Strategic Form Games

In this paper, I develop a syntactic framework for the analysis ofstrategic form games that is based on a straightforward combination ofstandard systems of doxastic, probabilistic and conditionalpropositional logic. In particular, for the probabilistic part I makeuse of the axiomatization provided in Fagin and Halpern (1994). The use ofconditionals allows to represent a strategic form game by a logicalformula in a very natural way. Also expected utility maximization can benaturally captured. I use this framework to prove a version of a resulton Nash equilibrium conjectures first presented in Aumann and Brandenburger (1995).