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

54th Annual IEEE Global Telecommunications Conference (GLOBECOM)

作者： Chaudhry, M. A. R. Asad, Z. Sprintson, A. Langberg, M. Texas A&M Univ Dept Elect & Comp Engn College Stn TX 77843 USA Open Univ Israel Raanana Israel

ISBN: (纸本)9781424492688

The Index Coding problem has recently attracted a significant attention from the research community. In this problem, a server needs to deliver data to a set of wireless clients over the broadcast channel. Each client requires one or more packets, but it might have access to the packets requested by other clients as side information. The goal is to deliver the required data to each client with minimum number of transmissions. In this paper, we focus on finding sparse solutions to the Index Coding problem. In a sparse solution each transmitted packet is a linear combination of at most two original packets. We focus both on scalar and vector versions of the problem. For the scalar case, we present a polynomial time algorithm that achieves an approximation ratio of 2 - 1/root n. For the vector case, we present a polynomial time algorithm that identifies an optimal solution to the problem. Our simulation studies demonstrate that our algorithms achieve good performance in practical scenarios.

关键词： Approximation algorithms Approximation methods Encoding Indexes Optimized production technology Servers Silicon carbide approximation ratio approximation theory broadcast channel client-server systems index coding problem linear combination network coding packet transmission packets access polynomial time algorithm polynomials radio networks research community scalar version sparse matrices sparse solution vector version wireless client

来源：评论

学校读者我要写书评

暂无评论

Minimum cost homomorphisms to reflexive digraphs

Minimum cost homomorphisms to reflexive digraphs

引用

8th Latin American Symposium on Theoretical Informatics (LATIN 2008)

作者： Gupta, Arvind Hell, Pavol Karimi, Mehdi Rafiey, Arash Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada

ISBN: (纸本)9783540787723

For a fixed digraph H, the minimum cost homomorphism problem, MinHOM(H), asks whether an input digraph G, with given costs c(i)(u), u is an element of V(G), i is an element of V(H), and an integer k, admits a homomorphism to H of total cost not exceeding k. Minimum cost homomorphism problems encompass many well studied optimization problems such as list homomorphism problems, retraction and precolouring extension problems, chromatic partition optimization, and applied problems in repair analysis. For undirected graphs the complexity of the problem, as a function of the parameter H, is well understood;for digraphs, the situation appears to be more complex, and only partial results are known. We focus on the minimum cost homomorphism problem for reflexive digraphs H. It is known that MinHOM(H) is polynomial if H has a Min-Max ordering. We prove that for any other reflexive digraph H, the problem MinHOM(H) is NP-complete. (This was earlier conjectured by Gutin and Kim.) Apart from undirected graphs, this is the first general class of digraphs for which such a dichotomy has been proved. Our proof involves a forbidden induced subgraph characterization of reflexive digraphs with a Min-Max ordering, and implies a polynomial test for the existence of a Min-Max ordering in a reflexive digraph H.

关键词： homomorphism minimum cost homomorphism reflexive digraph polynomial time algorithm NP-completeness dichotomy

来源：评论

学校读者我要写书评

暂无评论

Scheduling subject to nonrenewable-resource constraints

引用

Operations Research Letters 1982年第2期1卷 52-55页

作者： Carlier, J. Rinnooy Kan, A.H.G. Université de Pierre et Marie Curie 75230 Paris Cédex 05 4 Place Jussieu France Econometrisch Instituut Erasmus University 3000 DR Rotterdam P.O. Box 1738 Netherlands

polynomially bounded solution methods are presented to solve a class of precedence constrained scheduling problems in which each job requires a certain amount of nonrenewable resource that is being consumed during its... 详细信息

关键词： nonrenewable resource polynomial time algorithm Scheduling

来源：评论

学校读者我要写书评

暂无评论

A hereditary view on efficient domination

A hereditary view on efficient domination

引用

10th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2011

作者： Milanic, Martin UP FAMNIT University of Primorska Glagoljaska 8 6000 Koper Slovenia UP PINT University of Primorska Muzejski trg 2 6000 Koper Slovenia

来源：评论

学校读者我要写书评

暂无评论

Increasing the edge connectivity by one in O(λn2 log(∗) n) expected time 8

Increasing the edge connectivity by one in O(λn2 log(∗) n)...

引用

8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2009

作者： Brinkmeier, Michael Technische Universaität Ilmenau Faculty of Computer Science and Automation Institute for Theoretical Computer Science Germany

来源：评论

学校读者我要写书评

暂无评论

polynomial algorithms for computing the isolated toughness of interval and split graphs

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2023年第17期35卷

作者： Li, Fengwei Ye, Qingfang Broersma, Hajo Zhang, Xiaoyan Ningbo Univ Finance & Econ Coll Basic Sci Ningbo Peoples R China Univ Twente Fac EEMCS Enschede Netherlands Nanjing Normal Univ Sch Math Sci Nanjing 210023 Jiangsu Peoples R China Nanjing Normal Univ Inst Math Nanjing 210023 Jiangsu Peoples R China

The isolated toughness i tau(G) of a noncomplete graph G is defined as: i tau(G)=min{|Y|i(G-Y):Y is an element of C(G),i(G-Y)>1}, where C(G) is the collection of all vertex cutsets of G and i(G - Y) stands for the number of isolated vertices in G - Y. If G is a complete graph, we set i tau(G)=infinity. This isolated toughness parameter is closely related to the existence of factors and fractional factors in graphs. These factors and fractional factors are well-studied within graph theory, and have various applications in several fields related to computer science. In this article, we pay our attention to the computational complexity of computing the isolated toughness. We present polynomial algorithms for computing the exact value of i tau(G) for interval graphs and for split graphs, two well-studied special graph classes.

关键词： factor fractional factor interval graph isolated toughness polynomial time algorithm split graph

来源：评论

学校读者我要写书评

暂无评论

On the computational complexity of the secure state-reconstruction problem

引用

AUTOMATICA 2022年 136卷 110083-110083页

作者： Mao, Yanwen Mitra, Aritra Sundaram, Shreyas Tabuada, Paulo Univ Calif Los Angeles Dept Elect & Comp Engn Los Angeles CA 90095 USA Univ Penn Dept Elect & Syst Engn Philadelphia PA 19104 USA Purdue Univ Sch Elect & Comp Engn W Lafayette IN 47907 USA

In this paper, we discuss the computational complexity of reconstructing the state of a linear system from sensor measurements that have been corrupted by an adversary. The first result establishes that the problem is, in general, NP-hard. We then introduce the notion of eigenvalue observability and show that the state can be reconstructed in polynomial time when each eigenvalue is observable by at least 2s + 1 sensors and at most s sensors are corrupted by an adversary. However, there is a gap between eigenvalue observability and the possibility of reconstructing the state despite attacks - this gap has been characterized in the literature by the notion of sparse observability. To better understand this, we show that when the A matrix of the linear system has unitary geometric multiplicity, the gap disappears, i.e., eigenvalue observability coincides with sparse observability, and there exists a polynomial time algorithm to reconstruct the state provided the state can be reconstructed. (C) 2021 Elsevier Ltd. All rights reserved.

关键词： Resilient state secure state-reconstruction Eigenvalue and sparse observability polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

On Optimistic and Pessimistic Bilevel Optimization Models for Demand Response Management

引用

ENERGIES 2021年第8期14卷 2095-2095页

作者： Kis, Tamas Kovacs, Andras Meszaros, Csaba Eotvos Lorand Res Network ELKH EPIC Ctr Excellence Prod Informat & Control Inst Comp Sci & Control SZTAKI Kende U 13-17 H-1111 Budapest Hungary

This paper investigates bilevel optimization models for demand response management, and highlights the often overlooked consequences of a common modeling assumption in the field. That is, the overwhelming majority of existing research deals with the so-called optimistic variant of the problem where, in case of multiple optimal consumption schedules for a consumer (follower), the consumer chooses an optimal schedule that is the most favorable for the electricity retailer (leader). However, this assumption is usually illegitimate in practice;as a result, consumers may easily deviate from their expected behavior during realization, and the retailer suffers significant losses. One way out is to solve the pessimistic variant instead, where the retailer prepares for the least favorable optimal responses from the consumers. The main contribution of the paper is an exact procedure for solving the pessimistic variant of the problem. First, key properties of optimal solutions are formally proven and efficiently solvable special cases are identified. Then, a detailed investigation of the optimistic and pessimistic variants of the problem is presented. It is demonstrated that the set of optimal consumption schedules typically contains various responses that are equal for the follower, but bring radically different profits for the leader. The main procedure for solving the pessimistic variant reduces the problem to solving the optimistic variant with slightly perturbed problem data. A numerical case study shows that the optimistic solution may perform poorly in practice, while the pessimistic solution gives very close to the highest profit that can be achieved theoretically. To the best of the authors' knowledge, this paper is the first to propose an exact solution approach for the pessimistic variant of the problem.

关键词： demand response bilevel optimization pessimistic case polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Optimal standalone data center renewable power supply using an offline optimization approach

引用

SUSTAINABLE COMPUTING-INFORMATICS & SYSTEMS 2022年 34卷

作者： Landre, Damien Nicod, Jean-Marc Varnier, Christophe Univ Bourgogne Franche Comte UFC CNRS ENSMMFEMTO ST Inst Besancon France

Because of the increasing energy consumption of data centers and their CO2 emissions, the ANR DATAZERO2 project aims to design autonomous data centers running solely on local renewable energy coupled with storage devices to overcome the intermittency issue. In order to optimize the use of renewable energy and storage devices, a MILP solver is usually in charge of assigning the power to be supplied to the data center. However, in order to reduce the computation time and make the approach scalable, it would be more appropriate to use a polynomial time algorithm. This paper aims at showing and proving that it is possible to provide an optimal power profile via a deterministic algorithm using a binary search approach. Considering the main constraints of the initial problem, numerous experimental results show similar results to those given by the MILP. These promising results encourage us to continue in this direction for proposing an efficient management of the data center power supply that takes uncertainty into account.

关键词： Green data center Renewable energy Power management strategy Operational research polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Finding the projection onto the intersection of a closed half-space and a variable box

引用

OPERATIONS RESEARCH LETTERS 2013年第3期41卷 259-264页

作者： Liu, Yong-Jin Wang, Shiyun Sun, Juhe Shenyang Aerosp Univ Fac Sci Shenyang 110136 Peoples R China

This paper considers the problem of projecting a vector on the intersection of a closed half-space and a variable box. We present a polynomial time algorithm that is based on a parametric approach for finding the explicit formulas for the metric projection. As an application, the proposed algorithm is applied to compute the metric projection over the epigraph of the Ky Fan k-norm functions. Computational results on large-scale random test problems are also reported in order to evaluate the algorithm and its complexity time. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Projection polynomial time algorithm Ky Fan k-norm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：