检索结果-内蒙古大学图书馆

arXiv 2020年

作者： Jansen, Klaus Lassota, Alexandra Maack, Marten Pikies, Tytus Department of Computer Science Faculty Of Engineering Kiel University Germany Department of Algorithms and System Modelling ETI Faculty Gdańsk University of Technology Poland

This paper considers parallel machine scheduling with incompatibilities between jobs. The jobs form a graph and no two jobs connected by an edge are allowed to be assigned to the same machine. In particular, we study the case where the graph is a collection of disjoint cliques. Scheduling with incompatibilities between jobs represents a well-established line of research in scheduling theory and the case of disjoint cliques has received increasing attention in recent years. While the research up to this point has been focused on the makespan objective, we broaden the scope and study the classical total completion time criterion. In the setting without incompatibilities, this objective is well known to admit polynomial time algorithms even for unrelated machines via matching techniques. We show that the introduction of incompatibility cliques results in a richer, more interesting picture. Scheduling on identical machines remains solvable in polynomial time, while scheduling on unrelated machines becomes APX-hard. We identify several more subcases of theses problems that are polynomial time solvable or NP-hard, respectively. Furthermore, we study the problem under the paradigm of fixed-parameter tractable algorithms (FPT). In particular, we consider a problem variant with assignment restrictions for the cliques rather than the jobs. We prove that it is NP-hard and can be solved in FPT time with respect to the number of cliques. Moreover, we show that the problem on unrelated machines can be solved in FPT time for reasonable parameters, e.g., the parameter pair: number of machines and maximum processing time. The latter result is a natural extension of known results for the case without incompatibilities and can even be extended to the case of total weighted completion time. All of the FPT results make use of n-fold Integer Programs that recently have received great attention by proving their usefulness for scheduling problems. Copyright © 2020, The Authors. All rights

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

Equitable colorings of L-corona products of cubic graphs

arXiv

引用

arXiv 2017年

作者： Furmańczyk, Hanna Kubale, Marek Institute of Informatics University of Gdańsk Wita Stwosza 57 Gdańsk80-308 Poland Department of Algorithms and System Modelling Gdańsk University of Technology Narutowicza 11/12 Gdańsk80-233 Poland

A graph G is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the number of vertices in any two sets differ by at most one. The smallest integer k for which such a coloring exists is known as the equitable chromatic number of G and it is denoted by χ=(G). In this paper the problem of determinig the value of equitable chromatic number for multicoronas of cubic graphs G ◦l H is studied. The problem of ordinary coloring of multicoronas of cubic graphs is solvable in polynomial time. The complexity of equitable coloring problem is an open question for these graphs. We provide some polynomially solvable cases of cubical multicoronas and give simple linear time algorithms for equitable coloring of such graphs which use at most χ=(G ◦l H) + 1 colors in the remaining cases. Copyright © 2017, The Authors. All rights reserved.

关键词： Graphic methods

来源：评论

学校读者我要写书评

暂无评论

Device-independent quantum key distribution based on measurement inputs

引用

Physical Review A 2015年第6期92卷 062304-062304页

作者： Ramij Rahaman Matthew G. Parker Piotr Mironowicz Marcin Pawłowski Department of Mathematics University of Allahabad Allahabad 211002 U.P. India Institute of Theoretical Physics & Astrophysics University of Gdańsk 80-952 Gdańsk Poland Department of Informatics University of Bergen Post Box-7803 5020 Bergen Norway Department of Algorithms and System Modelling Faculty of Electronics Telecommunications and Informatics Gdańsk University of Technology Gdańsk 80-233 Poland National Quantum Information Centre in Gdańsk Sopot 81-824 Poland

We provide an analysis of a family of device-independent quantum key distribution (QKD) protocols that has the following features. (a) The bits used for the secret key do not come from the results of the measurements on an entangled state but from the choices of settings. (b) Instead of a single security parameter (a violation of some Bell inequality) a set of them is used to estimate the level of trust in the secrecy of the key. The main advantage of these protocols is a smaller vulnerability to imperfect random number generators made possible by feature (a). We prove the security and the robustness of such protocols. We show that using our method it is possible to construct a QKD protocol which retains its security even if the source of randomness used by communicating parties is strongly biased. As a proof of principle, an explicit example of a protocol based on the Hardy's paradox is presented. Moreover, in the noiseless case, the protocol is secure in a natural way against any type of memory attack, and thus allows one to reuse the device in subsequent rounds. We also analyze the robustness of the protocol using semidefinite programming methods. Finally, we present a postprocessing method, and observe a paradoxical property that rejecting some random part of the private data can increase the key rate of the protocol.

关键词： Quantum mechanics Quantum cryptography Distributed network protocols Quantum theory Quantum entanglement Telecommunication protocols -- Mathematical models Semidefinite programming Bell's theorem

来源：评论

学校读者我要写书评

暂无评论

Robust amplification of Santha-Vazirani sources with three devices

引用

Physical Review A 2015年第3期91卷 032317-032317页

作者： Piotr Mironowicz Rodrigo Gallego Marcin Pawłowski Department of Algorithms and System Modelling Faculty of Electronics Telecommunications and Informatics Gdańsk University of Technology Gdańsk 80-233 Poland National Quantum Information Centre in Gdańsk Sopot 81-824 Poland Dahlem Center for Complex Quantum Systems Freie Universitaet Berlin 14195 Berlin Germany Department of Mathematics University of Bristol Bristol BS8 1TW United Kingdom Institute of Theoretical Physics and Astrophysics University of Gdańsk 80-952 Gdańsk Poland

We demonstrate that amplification of arbitrarily weak randomness is possible using quantum resources. We present a randomness amplification protocol that involves Bell experiments. We find a Bell inequality that can amplify arbitrarily weak randomness and give a detailed analysis of the protocol involving it. Our analysis includes finding a sufficient violation of the Bell inequality as a function of the initial quality of randomness. It has a very important property that for any quality the required violation is strictly lower than possible to obtain using quantum resources. Among other things, this means that the protocol takes a finite amount of time to amplify arbitrarily weak randomness.

关键词： ROBUST control BELL'S theorem QUANTUM mechanics QUANTUM information theory QUANTUM cryptography

来源：评论

学校读者我要写书评

暂无评论

Properties of dimension witnesses and their semidefinite programming relaxations

引用

Physical Review A 2014年第2期90卷 022322-022322页

作者： Piotr Mironowicz Hong-Wei Li Marcin Pawłowski Department of Algorithms and System Modelling Faculty of Electronics Telecommunications and Informatics Gdańsk University of Technology Gdańsk 80-233 Poland National Quantum Information Centre in Gdańsk Sopot 81-824 Poland Key Laboratory of Quantum Information University of Science and Technology of China Hefei 230026 China Zhengzhou Information Science and Technology Institute Zhengzhou 450004 China Institute of Theoretical Physics and Astrophysics University of Gdańsk 80-952 Gdańsk Poland

In this paper we develop a method for investigating semi-device-independent randomness expansion protocols that was introduced in Li et al. [H.-W. Li, P. Mironowicz, M. Pawłowski, Z.-Q. Yin, Y.-C. Wu, S. Wang, W. Chen, H.-G. Hu, G.-C. Guo, and Z.-F. Han, Phys. Rev. A 87, 020302(R) (2013)]. This method allows us to lower bound, with semi-definite programming, the randomness obtained from random number generators based on dimension witnesses. We also investigate the robustness of some randomness expanders using this method. We show the role of an assumption about the trace of the measurement operators and a way to avoid it. The method is also generalized to systems of arbitrary dimension and for a more general form of dimension witnesses than in our previous paper. Finally, we introduce a procedure of dimension witness reduction, which can be used to obtain from an existing witness a new one with a higher amount of certifiable randomness. The presented methods find an application for experiments [J. Ahrens, P. Badziag, M. Pawlowski, M. Zukowski, and M. Bourennane, Phys. Rev. Lett. 112, 140401 (2014)].

关键词： SEMIDEFINITE programming RELAXATION (Nuclear physics) RANDOM number generators ROBUST control QUANTUM information theory

来源：评论

学校读者我要写书评

暂无评论

Robustness of quantum-randomness expansion protocols in the presence of noise

引用

Physical Review A 2013年第3期88卷 032319-032319页

作者： Piotr Mironowicz Marcin Pawłowski Department of Algorithms and System Modelling Faculty of Electronics Telecommunications and Informatics Gdańsk University of Technology Gdańsk 80-233 Poland National Quantum Information Centre in Gdańsk Sopot 81-824 Poland Department of Mathematics University of Bristol Bristol BC8 1TW United Kingdom Institute of Theoretical Physics and Astrophysics University of Gdańsk 80-952 Gdańsk Poland

In this paper we investigate properties of several randomness generation protocols in the device-independent framework. Using Bell-type inequalities it is possible to certify that the numbers generated by an untrusted device are indeed random. We present a selection of certificates which guarantee two bits of randomness for each run of the experiment in the noiseless case and require the parties to share a maximally entangled state. To compare them we study their efficiency in the presence of white noise. We find that for different amounts of noise different operators are optimal for certifying most randomness. Therefore, the vendor of the device should use different protocols depending on the amount of noise expected to occur. Another of our results that we find particularly interesting is that using a single Bell operator as a figure of merit is rarely optimal.

关键词： QUANTUM entanglement BELL'S theorem QUANTUM noise RANDOM number generators QUANTUM information theory QUANTUM entropy

来源：评论

学校读者我要写书评

暂无评论

Rearrangeability in multicast Clos networks is NP-complete

Rearrangeability in multicast Clos networks is NP-complete

引用

作者： Jastrzȩbski, Andrzej Kubale, Marek Department of Algorithms and System Modelling Gdansk University of Technology Gdansk Poland

ISBN: (纸本)9788360779026

Three-stage Clos networks are commutation networks with circuit switching. So far, graph theory has been very useful tool for solving issues related to these networks with unicast connections. This is so because if Clos network is represented as a bipartite graph then connecting paths are easy transformed into edge coloring. It is also natural to use on-line edge coloring algorithms. However, the things get more complicated in case of multicast connections. There are four models of multicast 3-stage Clos networks: model-l where only the first stage switches do not have fan-out capability, model-2 where only the second stage switches do not have fan-out capability, model-3 where only the third stage switches do not have fan-out capability and model-0 where no switches lack fanout capability. In the paper we show some new results on model-0 and model-l multicast Clos networks. In particular, we focus on rearrangeable multicast networks and prove that the problem of their rearranging is NP-complete.

关键词： Multicasting

来源：评论

学校读者我要写书评

暂无评论

Rearrangeability in multicast clos networks is np-complete

Rearrangeability in multicast clos networks is np-complete

引用

International Conference on Information Technology (ICIT)

作者： Andrzej Jastrzębski Marek Kubale Department of Algorithms and System Modelling Gdansk University of Technology Gdansk Poland

Three-stage Clos networks are commutation networks with circuit switching. So far, graph theory has been very useful tool for solving issues related to these networks with unicast connections. This is so because if Clos network is represented as a bipartite graph then connecting paths are easy transformed into edge coloring. It is also natural to use on-line edge coloring algorithms. However, the things get more complicated in case of multicast connections. There are four models of multicast 3-stage Clos networks: model-1 where only the first stage switches do not have fan-out capability, model-2 where only the second stage switches do not have fan-out capability, model-3 where only the third stage switches do not have fan-out capability and model-0 where no switches lack fan-out capability. In the paper we show some new results on model-0 and model-1 multicast Clos networks. In particular, we focus on rearrangeable multicast networks and prove that the problem of their rearranging is NP-complete.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Seaanning networks with cactus topology

Seaanning networks with cactus topology

引用

2008 1st International Conference on Information Technology, IT 2008

作者： Wrona, Lukasz Algorithms and System Modelling Department Gdansk Univeristy of Technology

ISBN: (纸本)9781424422456

The family of Pursuit and Evasion problems is widely studied because of its numerous practical applications, ranging from communication protocols to cybernetic and physical security. Calculating the search number of a graph is one of most commonly analyzed members of this problem family. The search number is the smallest number of mobile agents required to capture an invisible and arbitrarily fast fugitive, for instance piece of malicious software, in a given graph. It is closely related, to some other well known graph parameters, such as treewidth and pathwidth, and has been studied in a wide range of variants (edge, node, mixed, monotonous, connected, distributed, and others). Calculating the edge search number of a general graph is NP-hard, while it can be computed in linear time for trees. Calculating the search number of cacti, however, has not yet been widely covered. In this work we focus on this class of graphs, as it may be used to model Token Ring networks as well as some other network topologies when we assume that backup links are present. We address the problem of calculating the search number, as well as generating search strategy for cacti. © IEEE.

关键词： Mobile agents

来源：评论

学校读者我要写书评

暂无评论

New scalable measure for comparing phylogenetic trees

New scalable measure for comparing phylogenetic trees

引用

2008 1st International Conference on Information Technology, IT 2008

作者： Malafiejska, Anna Gdansk University of Technology Algorithms and System Modelling Department

ISBN: (纸本)9781424422456

The problem of comparing phylogenetic trees is based on finding a distance between different models of evolution. This problem is important because of existing various methods for reconstructing phytogenies, which applied to the same data set result in different trees. In the paper we construct a measure in a polynomial time using new structures called i-clusters. We analyze properties of i-clusters and prove that the measure is a metric in some space of rooted phylogenetic trees. The constructed measure is parametrized and the scalability parameter may be defined by user according to the reed data size and. complexity. The presented measure is the extension of widely applied error metric, defined, by Robinson and. Foulds in 1981. The generalization enables us to ommit small mistakes on low level and not to loose similarity of compared trees on high level. © IEEE.

关键词： Bioinformatics

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：