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

Improved decoding of Reed-Solomon and algebraic-geometry codes

IEEE TRANSACTIONS ON INFORMATION THEORY 1999年第6期45卷 1757-1767页

作者： Guruswami, V Sudan, M MIT Comp Sci Lab Cambridge MA 02139 USA

Given an error-correcting code over strings of length n and an arbitrary input string also of length n, the List decoding problem is that of finding all codewords within a specified Ramming distance from the input string. me present an improved list decoding algorithm for decoding Reed-Solomon codes, The list decoding problem for Reed-Solomon codes reduces to the following "curve-fitting" problem over a field F: Given n points {(x(i).y(i))}(i=1)(n), x(i) ,y(i) is an element of F, and a degree parameter L and error parameter e, find all univariate polynomials p of degree at most I;such that y(i) = p(x(i)) for all but at most e values of i is an element of {1, ..., n}, We give an algorithm that solves this problem for e < n - root kn, which improves over the previous best result [27], for every choice of k and n, Of particular interest is the ease of k/n > 1/3, where the result yields the first asymptotic improvement in four decades [21], The algorithm generalizes to solve the list decoding problem for other algebraic codes, specifically alternant codes (a class of codes including BCH codes) and algebraic-geometry codes. In both cases, we obtain a list decoding algorithm that corrects up to n - root n(n - d') errors, where n is the block length and d' is the designed distance of the code. The improvement for the case of algebraic-geometry codes extends the methods of [24] and improves upon their bound for every choice of n and d'. We also present some other consequences of our algorithm including a solution to a weighted curve-fitting problem, which may be of use in soft-decision decoding algorithms for Reed-Solomon codes.

关键词： algebraic-geometry codes decoding algorithms error-correcting codes list decoding polynomial time algorithms Reed-Solomon codes

来源：评论

学校读者我要写书评

暂无评论

Antidirected hamiltonian paths between specified vertices of a tournament

引用

DISCRETE APPLIED MATHEMATICS 2002年第1-3期117卷 87-98页

作者： Hell, P Rosenfeld, M Simon Fraser Univ Sch Comp Sci Dept Comp Sci Burnaby BC V5A 1S6 Canada Univ Washington Comp & Software Syst Program Tacoma WA 98402 USA

We prove that in any tournament there is an antidirected hamiltonian path from a specified first vertex to a specified last vertex, and starting with an arc of specified direction, as long as both the first vertex and the last vertex satisfy an obvious minimally necessary condition. We apply this result to give a polynomial time algorithm to find an antidirected hamiltonian path between two specified vertices of an input tournament. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： tournaments hamiltonian paths antidirected paths polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

Bicriteria scheduling concerned with makespan and total completion time subject to machine availability constraints

引用

THEORETICAL COMPUTER SCIENCE 2011年第12-14期412卷 1081-1091页

作者： Huo, Yumei Zhao, Hairong CUNY Coll Staten Isl Dept Comp Sci Staten Isl NY 10314 USA Purdue Univ Calumet Dept Math Comp Sci & Stat Hammond IN 46323 USA

In the past, research on multiple criteria scheduling assumes that the number of available machines is fixed during the whole scheduling horizon and research on scheduling with limited machine availability assumes that there is only a single criterion that needs to be optimized. Both assumptions may not hold in real life. In this paper we simultaneously consider both bicriteria scheduling and scheduling with limited machine availability. We focus on two parallel machines' environment and the goal is to find preemptive schedules to optimize both makespan and total completion time subject to machine availability. Our main contribution in this paper is that we showed three bicriteria scheduling problems are in P by providing polynomial time optimal algorithms. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Bicriteria scheduling Machine availability constraint Makespan Total completion time polynomial time algorithms Two machine

来源：评论

学校读者我要写书评

暂无评论

Negotiation as concurrency primitive

引用

ACTA INFORMATICA 2019年第2期56卷 93-159页

作者： Desel, Joerg Esparza, Javier Hoffmann, Philipp Fernuniv Hagen Germany Tech Univ Munich Munich Germany

This paper introduces negotiations, a model of concurrency close to Petri nets, with multi-party negotiations as concurrency primitive. We study two fundamental analysis problems. The soundness problem consists in deciding if it is always possible for a negotiation to terminate successfully, whatever the current state is. Given a sound negotiation, the summarization problem aims at computing an equivalent one-step negotiation with the same input/output behavior. The soundness and summarization problems can be solved by means of simple algorithms acting on the state space of the negotiation, which however face the well-known state explosion problem. We study alternative algorithms that avoid the construction of the state space. In particular, we define reduction rules that simplify a negotiation while preserving the sound/non-sound character of the negotiation and its summary. In a first result we show that our rules are complete for the class of weakly deterministic acyclic negotiations, meaning that they reduce all sound negotiations in this class, and only them, to equivalent one-step negotiations. This provides algorithms for both the soundness and the summarization problem that avoid the construction of the state space. We then study the class of deterministic negotiations. Our second main result shows that the rules are also complete for this class, even if the negotiations contain cycles. Moreover, we present an algorithm that completely reduces all sound deterministic negotiations, and only them, in polynomial time.

关键词： NEGOTIATION INVESTMENT analysis TRANSFORMATIONS (Mathematics) polynomial time algorithms PLEONASM

来源：评论

学校读者我要写书评

暂无评论

Isomorphism of regular trees and words

引用

INFORMATION AND COMPUTATION 2013年 224卷 71-105页

作者： Lohrey, Markus Mathissen, Christian Univ Leipzig Inst Informat Leipzig Germany

The computational complexity of the isomorphism problem for regular trees, regular linear orders, and regular words is analyzed. A tree is regular if it is isomorphic to the prefix order on a regular language. In case regular languages are represented by NFAs (DFAs), the isomorphism problem for regular trees turns out to be EXPtime-complete (resp. P-complete). In case the input automata are acyclic NFAs (acyclic DFAs), the corresponding trees are (succinctly represented) finite trees, and the isomorphism problem turns out to be PSPACE-complete (resp. P-complete). A linear order is regular if it is isomorphic to the lexicographic order on a regular language. A polynomial time algorithm for the isomorphism problem for regular linear orders (and even regular words, which generalize the latter) given by DFAs is presented. This solves an open problem by Esik and Bloom. Similar techniques can be used to show that one can check in polynomial time whether a given regular linear order has a non-trivial automorphism. This improves a recent decidability result of Kuske. (C) 2013 Elsevier Inc. All rights reserved.

关键词： ISOMORPHISMS (Mathematics) COMPUTATIONAL complexity MACHINE theory LEXICOGRAPHY polynomial time algorithms AUTOMORPHISMS

来源：评论

学校读者我要写书评

暂无评论

A combinatorial polynomial algorithm for the linear Arrow-Debreu market

引用

INFORMATION AND COMPUTATION 2015年 243卷 112-132页

作者： Duan, Ran Mehlhorn, Kurt Max Planck Inst Informat D-66123 Saarbrucken Germany

We present the first combinatorial polynomial time algorithm for computing the equilibrium of the Arrow-Debreu market model with linear utilities. Our algorithm views the allocation of money as flows and iteratively improves the balanced flow as in [11] for Fisher's model. We develop new methods to carefully deal with the flows and surpluses during price adjustments. Our algorithm performs O(n(6)log(nU)) maximum flow computations, where n is the number of agents and U is the maximum integer utility. The flows have to be presented as numbers of bitlength O(n log(nU)) to guarantee an exact solution. Previously, [22,29] have given polynomial time algorithms for this problem, which are based on solving convex programs using the ellipsoid algorithm and the interior-point method, respectively. (C) 2014 Elsevier Inc. All rights reserved.

关键词： COMBINATORIAL analysis polynomial time algorithms MARKETS PROBLEM solving MATHEMATICAL models INTERIOR-point methods

来源：评论

学校读者我要写书评

暂无评论

A Fast Algorithm for Augmenting Edge-Connectivity by One with Bipartition Constraints

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2012年第3期E95D卷 769-777页

作者： Oki, Tadachika Taoka, Satoshi Mashima, Toshiya Watanabe, Toshimasa Hiroshima Univ Grad Sch Engn Higashihiroshima 7398527 Japan Hiroshima Int Univ Fac Engn Dept Informat & Commun Technol Kure 7370112 Japan

The k-edge-connectivity augmentation problem with bipartition constraints (kECABP, for short) is defined by "Given an undirected graph G = (V, E) and a bipartition pi = {V-B, V-W} of V with V-B boolean AND V-W = theta, find an edge set E-f of minimum cardinality, consisting of edges that connect V-B and V-w, such that G' = (V, E boolean OR E-f) is k-edge-connected." The problem has applications for security of statistical data stored in a cross tabulated table, and so on. In this paper we propose a fast algorithm for finding an optimal solution to (sigma + 1)ECABP in O(vertical bar V vertical bar vertical bar E vertical bar + vertical bar V-2 vertical bar log vertical bar V vertical bar) time when G is sigma-edge-connected (sigma > 0), and show that the problem can be solved in linear time if sigma is an element of {1, 2}.

关键词： connectivity augmentation problems edge-connectivity bipartition constraints graphs polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

Single batch machine scheduling with deliveries

引用

NAVAL RESEARCH LOGISTICS 2015年第6期62卷 470-482页

作者： Cheng, B. -Y. Leung, J. Y. -T. Li, K. Yang, S. -L. Hefei Univ Technol Sch Management Hefei 230009 Peoples R China Minist Educ Key Lab Proc Optimizat & Intelligent Decis Making Hefei 230009 Peoples R China New Jersey Inst Technol Dept Comp Sci Newark NJ 07012 USA

We consider the problem of scheduling a set of n jobs on a single batch machine, where several jobs can be processed simultaneously. Each job j has a processing time p(j) and a size s(j). All jobs are available for processing at time 0. The batch machine has a capacity D. Several jobs can be batched together and processed simultaneously, provided that the total size of the jobs in the batch does not exceed D. The processing time of a batch is the largest processing time among all jobs in the batch. There is a single vehicle available for delivery of the finished products to the customer, and the vehicle has capacity K. We assume that K=rD, where r >= 2 and r is an integer. The travel time of the vehicle is T;that is, T is the time from the manufacturer to the customer. Our goal is to find a schedule of the jobs and a delivery plan so that the service span is minimized, where the service span is the time that the last job is delivered to the customer. We show that if the jobs have identical sizes, then we can find a schedule and delivery plan in O(n log n) time such that the service span is minimum. If the jobs have identical processing times, then we can find a schedule and delivery plan in O(n log n) time such that the service span is asymptotically at most 11/9 times the optimal service span. When the jobs have arbitrary processing times and arbitrary sizes, then we can find a schedule and delivery plan in O(n log n) time such that the service span is asymptotically at most twice the optimal service span. We also derive upper bounds of the absolute worst-case ratios in both cases. (c) 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 470-482, 2015

关键词： batch machine scheduling delivery polynomial time algorithms NP-hard approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

On Computing Discrete Logarithms in Bulk and Randomness Extractors

引用

FUNDAMENTA INFORMATICAE 2015年第4期141卷 343-364页

作者： Durnoga, Konrad Zralek, Bartosz Univ Warsaw Inst Informat PL-02097 Warsaw Poland

We prove several results of independent interest related to the problem of computing deterministically discrete logarithms in a finite field. The motivation was to give a number-theoretic construction of a non-malleable extractor improving the solution from the recent paper Privacy Amplification and Non-Malleable Extractors via Character Sums by Dodis et al. There, the authors provide the first explicit example of a non-malleable extractor - a cryptographic primitive that significantly strengthens the notion of a classical randomness extractor. In order to make the extractor robust, so that it runs in polynomial time and outputs a linear number of bits, they rely on a certain conjecture on the least prime in a residue class. In this work we present a modification of their construction that allows to remove that dependency and address an issue we identified in the original development. Namely, it required an additional assumption about feasibility of finding a primitive element of a finite field. As an auxiliary result, we show an efficiently computable bijection between any order M subgroup of the multiplicative group of a finite field and a set of integers modulo M with the provision that M is a smooth number. Also, we provide a version of the baby-step giant-step method for solving multiple instances of the discrete logarithm problem in the multiplicative group of a prime field. It performs better than the generic algorithm when run on a machine without constant-time access to each memory cell, e.g., on a classical Turing machine.

关键词： Logarithms Mathematical proofs Finite fields (Algebra) Number theory Cryptography polynomial time algorithms Integers

来源：评论

学校读者我要写书评

暂无评论

Some inverse min-max network problems under weighted l₁ and l_∞ norms with bound constraints on changes

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2007年第2期13卷 123-135页

作者： Yang, Xiaoguang Zhang, Jianzhong Chinese Acad Sci Acad Math & Syst Sci Beijing 100080 Peoples R China Chinese Univ Hong Kong Dept Syst Engn & Engn Management Hong Kong Hong Kong Peoples R China

We consider some inverse min-max (or max-min) network problems. Such an inverse problem is to modify the weights with bound constraints so that a given feasible solution becomes an optimal solution of a min-max (or max-min) network problem, and the deviation of the weights, measured by the weighted l(1) norm or weighted 1(infinity) norm, is minimum. In this paper, we present strongly polynomial time algorithms to solve the inverse min-max spanning tree problem and the inverse maximum capacity path problem.

关键词： inverse min-max network problem weighted l(1) norm weighted l(infinity) norm bound constraints polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：