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

A New Lower Bound for Classic Online Bin Packing

ALGORITHMICA 2021年第7期83卷 2047-2062页

作者： Balogh, Janos Bekesi, Jozsef Dosa, Gyorgy Epstein, Leah Levin, Asaf Univ Szeged Inst Informat Szeged Hungary Univ Pannonia Dept Math Veszprem Hungary Univ Haifa Dept Math Haifa Israel Technion Fac Ind Engn & Management Haifa Israel

We improve the lower bound on the asymptotic competitive ratio of any online algorithm for bin packing to above 1.54278. We demonstrate for the first time the advantage of branching and the applicability of full adaptivity in the design of lower bounds for the classic online bin packing problem. We apply a new method for weight based analysis, which is usually applied only in proofs of upper bounds. The values of previous lower bounds were approximately 1.5401 and 1.5403.

关键词： Algorithm Analysis and Problem Complexity theory of Computation Mathematics of Computing Algorithms Computer Systems Organization and Communication Networks data structures and information theory

来源：评论

学校读者我要写书评

暂无评论

Equilibria for games with combined qualitative and quantitative objectives

引用

ACTA INFORMATICA 2021年第6期58卷 585-610页

作者： Gutierrez, Julian Murano, Aniello Perelli, Giuseppe Rubin, Sasha Steeples, Thomas Wooldridge, Michael Monash Univ Melbourne Vic Australia Univ Naples Federico II Naples Italy Sapienza Univ Rome Rome Italy Univ Sydney Sydney NSW Australia Univ Oxford Oxford England

The overall aim of our research is to develop techniques to reason about the equilibrium properties of multi-agent systems. We model multi-agent systems as concurrent games, in which each player is a process that is assumed to act independently and strategically in pursuit of personal preferences. In this article, we study these games in the context of finite-memory strategies, and we assume players' preferences are defined by a qualitative and a quantitative objective, which are related by a lexicographic order: a player first prefers to satisfy its qualitative objective (given as a formula of linear temporal logic) and then prefers to minimise costs (given by a mean-payoff function). Our main result is that deciding the existence of a strict epsilon Nash equilibrium in such games is 2ExpTime-complete (and hence decidable), even if players' deviations are implemented as infinite-memory strategies.

关键词： Logics and Meanings of Programs Computer Systems Organization and Communication Networks Software Engineering/Programming and Operating Systems data structures and information theory theory of Computation information Systems and Communication Service

来源：评论

学校读者我要写书评

暂无评论

Near Isometric Terminal Embeddings for Doubling Metrics

引用

ALGORITHMICA 2021年第11期83卷 3319-3337页

作者： Elkin, Michael Neiman, Ofer Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

Given a metric space (X, d), a set of terminals K subset of X, and a parameter 0 < epsilon < 1, we consider metric structures (e.g., spanners, distance oracles, embedding into normed spaces) that preserve distances for all pairs in K x X up to a factor of 1 + epsilon, and have small size (e.g. number of edges for spanners, dimension for embeddings). While such terminal (aka source-wise) metric structures are known to exist in several settings, no terminal spanner or embedding with distortion close to 1, is currently known. Here we devise such terminal metric structures for doubling metrics, and show that essentially any metric structure with distortion 1 + epsilon and space s(vertical bar X vertical bar) has its terminal counterpart, with distortion 1 + O(epsilon) and space s(vertical bar K vertical bar) + n. In particular, for any doubling metric on n points, a set of k terminals, and constant 0 < epsilon < 1, there exists A spanner with stretch 1 + epsilon for pairs in K x X, with n + O(k) edges. A labeling scheme with stretch 1 + epsilon for pairs in K x X, with label size approximate to log k. An embedding into l(infinity)(d) with distortion 1 + epsilon for pairs in K x X, where d = O(log k). Moreover, surprisingly, the last two results apply if only the metric space on K is doubling, while the metric on X can be arbitrary.

来源：评论

学校读者我要写书评

暂无评论

Complement for two-way alternating automata

引用

ACTA INFORMATICA 2021年第5期58卷 463-495页

作者： Geffert, Viliam Kapoutsis, Christos A. Zakzok, Mohammad Safarik Univ Dept Comp Sci Kosice Slovakia Carnegie Mellon Univ Qatar Dept Comp Sci Doha Qatar

We consider the problem of converting a two-way alternating finite automaton (2AFA) with n states to a 2AFA accepting the complement of its language. Complementing is trivial for halting2AFAs, by swapping the roles of existential and universal decisions and the roles of accepting and rejecting states. However, since 2AFAs do not have resources to detect infinite loops by counting executed steps, it was not known whether the cost of complementing is polynomial in n in the general case. Here we shall show that 2AFAs can be complemented by using O(n(7)) states.

来源：评论

学校读者我要写书评

暂无评论

Special issue on Sentient Multimedia Systems

引用

MULTIMEDIA TOOLS AND APPLICATIONS 2022年第1期81卷 51-54页

作者： Caruccio, Loredana Polese, Giuseppe Chang, Shi-Kuo Univ Salerno Fisciano Italy Univ Pittsburgh Pittsburgh PA USA

来源：评论

学校读者我要写书评

暂无评论

European data infrastructures: Approaches and tools for the use of data for the benefit of the individual and the community

引用

Informatik-Spektrum 2021年第4期44卷 283-291页

作者： Otto, Boris Burmann, Anja Fraunhofer-Institut für Software- und Systemtechnik ISST Emil-Figge-Straße 91 Dortmund44227 Germany Lehrstuhl für Industrielles Informationsmanagement Technische Universität Dortmund Joseph-von-Fraunhofer-Str. 2–4 Dortmund44227 Germany

Zusammenfassung Daten stellen eine strategische Ressource für die Wettbewerbsfähigkeit von Unternehmen und die Prosperität der Gesellschaft dar. Von der Nutzung von Daten vieler einzelner Akteure profitieren die Gemeinschaft, aber auch das Individuum. Beispiele hierfür liefern das Gesundheitswesen oder die Mobilität. Dabei sind die Interessen der Individuen in Bezug auf Datenschutz und Datensouveränität über Nutzungsvereinbarungen hinaus zu wahren und bestenfalls technologisch sicherzustellen. Datenräume, basierend auf verteilten Dateninfrastrukturen, stellen Datendienste und Datennutzungsregeln für Individuen und Organisationen bereit. Beispiele hierfür liefern die International-data-Spaces(IDS)-Initiative oder die Initiative Gaia‑X zur Schaffung einer verteilten Dateninfrastruktur in Europa. Instanziierungen in den Bereichen Mobilität oder Smarthome zeigen Vorteile von Datenökosystemen für Individuen, die Gemeinschaft und die Gesamtheit der Dienstanbieter. Gleichzeitig werden Risiken wie die geeignete Interessensvertretung einzelner Nutzender deutlich. Anhand zweier Fallstudien werden offene ethische, rechtliche, betriebswirtschaftliche und technische Fragen bei der verteilten Umsetzung von Datenräumen und Dateninfrastrukturen unter Sicherstellung europäischer Wertevereinbarungen aufgezeigt.

关键词： Computer Science general Computer Hardware Computer Systems Organization and Communication Networks Software Engineering/Programming and Operating Systems data structures and information theory

来源：评论

学校读者我要写书评

暂无评论

Session-based concurrency, declaratively

引用

ACTA INFORMATICA 2022年第1期59卷 35-87页

作者： Cano, Mauricio Lopez, Hugo A. Perez, Jorge A. Rueda, Camilo Univ Groningen Groningen Netherlands Univ Copenhagen Copenhagen Denmark DCR Solut AS Copenhagen Denmark CWI Amsterdam Netherlands Pontificia Univ Javeriana Cali Valle Del Cauca Colombia

Session-based concurrency is a type-based approach to the analysis of message-passing programs. These programs may be specified in an operational or declarative style: the former defines how interactions are properly structured;the latter defines governing conditions for correct interactions. In this paper, we study rigorous relationships between operational and declarative models of session-based concurrency. We develop a correct encoding of session pi-calculus processes into the linear concurrent constraint calculus (lcc), a declarative model of concurrency based on partial information (constraints). We exploit session types to ensure that our encoding satisfies precise correctness properties and that it offers a sound basis on which operational and declarative requirements can be jointly specified and reasoned about. We demonstrate the applicability of our results by using our encoding in the specification of realistic communication patterns with time and contextual information.

来源：评论

学校读者我要写书评

暂无评论

Indecision and delays are the parents of failure-taming them algorithmically by synthesizing delay-resilient control

引用

ACTA INFORMATICA 2021年第5期58卷 497-528页

作者： Chen, Mingshuai Fraenzle, Martin Li, Yangjia Mosaad, Peter N. Zhan, Naijun Rhein Westfal TH Aachen Lehrstuhl Informat 2 Aachen Germany Carl von Ossietzky Univ Oldenburg Dept Comp Sci Oldenburg Germany Univ Tartu Tartu Estonia Chinese Acad Sci Inst Software State Key Lab Comp Sci Beijing Peoples R China Univ Chinese Acad Sci Beijing Peoples R China

The possible interactions between a controller and its environment can naturally be modelled as the arena of a two-player game, and adding an appropriate winning condition permits to specify desirable behavior. The classical model here is the positional game, where both players can (fully or partially) observe the current position in the game graph, which in turn is indicative of their mutual current states. In practice, neither sensing and actuating the environment through physical devices nor data forwarding to and from the controller and signal processing in the controller are instantaneous. The resultant delays force the controller to draw decisions before being aware of the recent history of a play and to submit these decisions well before they can take effect asynchronously. It is known that existence of a winning strategy for the controller in games with such delays is decidable over finite game graphs and with respect to omega regular objectives. The underlying reduction, however, is impractical for non-trivial delays as it incurs a blow-up of the game graph which is exponential in the magnitude of the delay. For safety objectives, we propose a more practical incremental algorithm successively synthesizing a series of controllers handling increasing delays and reducing the game-graph size in between. It is demonstrated using benchmark examples that even a simplistic explicit-state implementation of this algorithm outperforms state-of-the-art symbolic synthesis algorithms as soon as non-trivial delays have to be handled. We furthermore address the practically relevant cases of non-order-preserving delays and bounded message loss, as arising in actual networked control, thereby considerably extending the scope of regular game theory under delay.

来源：评论

学校读者我要写书评

暂无评论

Special issue on quantum computing with superconducting qubits

引用

QUANTUM information PROCESSING 2009年第2-3期8卷 51-54页

作者： Korotkov, Alexander N. Univ Calif Riverside Dept Elect Engn Riverside CA 92521 USA

Quantum state control including entanglement, and readout of the Josephson persistent-current qubit, flux qubit, are reviewed. First, we mention our single-shot readout of quantum superposition state of a flux qubit by a current biased dc-SQUID. Second, we mention entangled state and vacuum Rabi oscillations of a flux-qubit LC-resonator system where qubit-resonator coupled state are controlled by a combination of microwave and DC-shift pulses, resulting in a controlling and measuring sequence analogous to atomic cavity QED. Third, we report our recent progress in high fidelity readout of a flux qubit state via Josephson bifurcation amplifier (JBA).

关键词： Quantum information Technology Spintronics Quantum Computing data structures and information theory Quantum Physics Mathematical Physics

来源：评论

学校读者我要写书评

暂无评论

Sound reasoning in tock-CSP

引用

ACTA INFORMATICA 2022年第1期59卷 125-162页

作者： Baxter, James Ribeiro, Pedro Cavalcanti, Ana Univ York Dept Comp Sci York N Yorkshire England

Specifying budgets and deadlines using a process algebra like CSP requires an explicit notion of time. The tock-CSP encoding embeds a rich and flexible approach for modelling discrete-time behaviours with powerful tool support. It uses an event tock, interpreted to mark passage of time. Analysis, however, has traditionally used the standard semantics of CSP, which is inadequate for reasoning about timed refinement. The most recent version of the model checker FDR provides tailored support for tock-CSP, including specific operators, but the standard semantics remains inadequate. In this paper, we characterise tock-CSP as a language in its own right, rich enough to model budgets and deadlines, and reason about Zeno behaviour. We present the first sound tailored semantic model for tock-CSP that captures timewise refinement. It is fully mechanised in Isabelle/HOL and, to enable use of FDR4 to check refinement in this novel model, we use model shifting, which is a technique that explicitly encodes refusals in traces.

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：