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

Deciding multiaffinity of polynomials over a finite field

DISCRETE MATHEMATICS AND APPLICATIONS 2024年第4期34卷 233-244页

作者： Selezneva, Svetlana N. Lomonosov Moscow State Univ Moscow Russia

We consider polynomials f(x1, & mldr;, xn) over a finite filed that satisfy the following condition: the set of solutions of the equation f(x1, & mldr;, xn) = b, where b is some element of the field, coincides with the set of solutions of some system of linear equations over this field. Such polynomials are said to be multiaffine with the right-hand side b (or with respect to b). We describe a number of properties of multiaffine polynomials. Then on the basis of these properties we propose a polynomial algorithm that takes a polynomial over a finite field and an element of the field as an input and decides whether the polynomial is multiaffine with respect to this element. In case of the positive answer the algorithm also outputs a system of linear equations that corresponds to this polynomial. The complexity of the proposed algorithm is the smallest in comparison with other known algorithms that solve this problem.

关键词： finite field polynomial multiaffinity system of linear equations over a finite field algorithm complexity polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

Identities of the Kauffman monoid K3

引用

COMMUNICATIONS IN ALGEBRA 2020年第5期48卷 1956-1968页

作者： Chen, Yuzhu Hu, Xun Kitov, Nikita, V Luo, Yanfeng Volkov, Mikhail V. Lanzhou Univ Dept Math & Stat Lanzhou Gansu Peoples R China Chongqing Technol & Business Univ Dept Math & Stat Chongqing Peoples R China Ural Fed Univ Inst Nat Sci & Math Lenina 51 Ekaterinburg 620000 Russia

We give a transparent combinatorial characterization of the identities satisfied by the Kauffman monoid Our characterization leads to a polynomial time algorithm to check whether a given identity holds in K-3.

关键词： Kauffman monoid Semigroup identity polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

A METHOD FOR MODELING THE STRUCTURE OF INITIAL DATA AND SUBCLASSES OF SOLVABLE COMBINATORIAL OPTIMIZATION PROBLEMS

引用

CYBERNETICS AND SYSTEMS ANALYSIS 2014年第1期50卷 1-7页

作者： Donets, G. A. Sergienko, I. V. Natl Acad Sci Ukraine VM Glushkov Inst Cybernet Kiev Ukraine

A class of polynomially solvable problems of combinatorial optimization is illustrated by the example of the traveling salesman problem. It is proved that this class includes problems for which the structure of initia... 详细信息

关键词： intractable problem polynomial algorithm NP-complete problem traveling salesman problem assignment problem solvable subclass of problems combinatorial optimization matrix of Supnik Kalmanson Demidenko and Monge

来源：评论

学校读者我要写书评

暂无评论

GENERAL APPROACH TO ESTIMATING THE COMPLEXITY OF POSTOPTIMALITY ANALYSIS FOR DISCRETE OPTIMIZATION PROBLEMS

引用

CYBERNETICS AND SYSTEMS ANALYSIS 2010年第2期46卷 290-295页

作者： Mikhailyuk, V. A. Natl Acad Sci Ukraine VM Glushkov Cybernet Inst Kiev Ukraine

It is shown that there does not exist a polynomial algorithm to derive the optimal solution of a set cover problem that differs from the original problem in one position of the constraint matrix if the optimal solutio... 详细信息

关键词： postoptimality analysis polynomial algorithm polynomially solvable problem

来源：评论

学校读者我要写书评

暂无评论

Finding blocks and other patterns in a random coloring of Z

引用

RANDOM STRUCTURES & algorithmS 2006年第1期28卷 37-75页

作者： Matzinger, H Rolles, SWW Georgia Inst Technol Sch Math Atlanta GA 30332 USA Univ Bielefeld Dept Math D-33501 Bielefeld Germany

Let xi := (xi(k))(k is an element of Z) be i.i.d. with P(xi(k) = 0) = P(xi(k) = 1) = 1/2, and let S := (S-k)(k is an element of N0) be a symmetric random walk with holding on Z, independent of. We consider the scenery observed along the random walk path S, namely, the process (X-k := xi s(k))(k is an element of N0) With high probability, we reconstruct the color and the length of block", a block in of length >= it close to the origin, given only the observations (X-k)(k is an element of[0,2.33n]). We find stopping times that stop the random walker with high probability at particular places of the scenery, namely on block" and in the interval [-3(n), 3(n)]. Moreover, we reconstruct with high probability a piece of of length of the order 3,0,2 around block", given only 3[n(0.3)] observations collected by the random walker starting on the boundary of block". (c) 2005 Wiley Periodicals, Inc.

关键词： random walk random media scenery reconstruction polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

On the jump number problem in hereditary classes of bipartite graphs

引用

ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS 2000年第4期17卷 377-385页

作者： Lozin, VV Gerber, MU Nizhny Novgorod Univ Nizhnii Novgorod 603600 Russia Swiss Fed Inst Technol Dept Math CH-1015 Lausanne Switzerland

We prove a necessary condition for polynomial solvability of the jump number problem in classes of bipartite graphs characterized by a finite set of forbidden induced bipartite subgraphs. For some classes satisfying t... 详细信息

关键词： bipartite graphs jump number polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

The vehicle routing problem with pickups and deliveries on some special graphs

引用

DISCRETE APPLIED MATHEMATICS 2002年第3期116卷 193-229页

作者： Tzoreff, TE Granot, D Granot, F Sosic, G Univ British Columbia Fac Commerce & Business Adm Vancouver BC V6T 1Z2 Canada

The vehicle routing with pickups and deliveries (VRPD) problem is defined over a graph G=(V,E). Some vertices in G represent delivery customers who expect deliveries from a depot, and other vertices in G represent pick-up customers who have available supply to be picked up and transported to a depot. The objective is to find a minimum length tour for a capacitated vehicle, which starts at a depot and travels in G while satisfying all the requests by the delivery and pickup customers, without violating the vehicle capacity constraint, and returns to a depot. We study the VRPD problem on some special graphs, including trees, cycles and warehouse graphs when the depots are both exogenously and endogenously determined. Specifically, we develop linear time algorithms for the VRPD problem on tree graphs and polynomial algorithms on cycle and warehouse graphs. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： vehicle routing polynomial algorithm tree cycle graphs warehouse graph

来源：评论

学校读者我要写书评

暂无评论

On a generalized single machine scheduling problem with time-dependent processing times

引用

IFAC-PapersOnLine 2016年第12期49卷 226-230页

作者： Lazarev, Alexander A. Arkhipov, Dmitry I. Werner, Frank V.A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences International Laboratory of Decision Choice and Analysis National Research University Higher School of Economics Lomonosov Moscow State University Moscow Institute of Physics and Technology Moscow Dolgoprudny Russia V.A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences Moscow Russia Faculty of Mathematics Institute of Mathematical Optimization Otto-von-Guericke University Magdeburg Germany

In this paper, a generalized formulation of a classical single machine scheduling problem is considered. A set of n jobs characterized by their release dates, deadlines and a start time-dependent processing time function p(t) has to be processed on a single machine. The objective is to find a Pareto-optimal set of schedules with respect to the criteria maxand makespan, where maxis a non-decreasing function depending on the completion times of the jobs. We present an approach that allows to find an optimal schedule with respect to different scheduling criteria, such as the minimization of makespan, lateness or weighted lateness, tardiness and weighted tardiness etc. in time polynomially depending on the number of jobs. The complexity of the presented algorithm is O(n3max{log n, H, P}), where H and P are the complexity of calculating j(t) and p(t), respectively. © 2016

关键词： Scheduling algorithms Machinery Pareto principle Scheduling Makespan Non decreasing functions Pareto set Pareto optimal sets polynomial algorithm Single machine scheduling problems Single machine scheduling Time dependent processing time

来源：评论

学校读者我要写书评

暂无评论

Computing remoteness functions of Moore, Wythoff, and Euclid's games

引用

INTERNATIONAL JOURNAL OF GAME THEORY 2024年第4期53卷 1315-1333页

作者： Boros, Endre Gurvich, Vladimir Makino, Kazuhisa Vyalyi, Michael Rutgers State Univ Business Sch MSIS & RUTCOR 100 Rockafellar Rd Piscataway NJ 08854 USA Kyoto Univ Res Inst Math Sci Kyoto Japan Natl Res Univ Higher Sch Econ HSE Moscow Russia Russian Acad Sci Fed Res Ctr Comp Sci & Control Moscow Russia Moscow Inst Phys & Technol Dept Control & Appl Math Dolgoprudnyi Russia

We study remoteness function R\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {R}}$$\end{document} of impartial games introduced by Smith in 1966. The player who moves from a position x can win if and only if R(x)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {R}}(x)$$\end{document} is odd. The odd values of R(x)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {R}}(x)$$\end{document} show how soon the winner can win, while even values show how long the loser can resist, provided both players play optimally. This function can be applied to the conjunctive compounds of impartial games, in the same way as the Sprague-Grundy function is applicable to their disjunctive compounds. We provide polynomial algorithms computing R(x)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {R}}(x)$$\end{document} for games Euclid and generalized Wythoff. For Moore's NIM we give a simple explicit formula for R(x)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {R}}(x)$$\end{document} if it is even and show that computing it becomes an NP-hard probl

关键词： Impartial games Sprague-Grundy function Smith's remoteness function NP completeness polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

Gray codes with bounded weights

引用

DISCRETE MATHEMATICS 2012年第17期312卷 2599-2611页

作者： Dvorak, Tomas Fink, Jiri Gregor, Petr Koubek, Vaclav Charles Univ Prague Fac Math & Phys Prague 11800 Czech Republic

Given a set H of binary vectors of length n, is there a cyclic listing of H so that every two successive vectors differ in a single coordinate? The problem of the existence of such a listing, which is called a cyclic Gray code of H, is known to be NP-complete in general. The goal of this paper is therefore to specify boundaries between its intractability and polynomial decidability. For that purpose, we consider a restriction when the vectors of H are of a bounded weight. A weight of a vector u is an element of {0, 1}(n) is the number of l's in u. We show that if every vertex of H has weight k or k + 1, our problem is decidable in polynomial time for k <= 1 and NP-complete for k >= 2. Furthermore, if k = 2 and for every i is an element of [n] there are at most m vectors of H of weight two having one in the i-th coordinate, then the problem becomes decidable in polynomial time for m <= 3 and NP-complete for m >= 13. The following complementary problem is also known to be NP-hard: given an F subset of (0, 1)(n), which now plays the role of a set of faults to be avoided, is there a cyclic Gray code of {0, 1}(n) \ F? We show that if every vertex of F has weight at most k, the problem is decidable in polynomial time for k <= 2 and NP-hard for k >= 5. It follows that there is a function f(n) = Theta(n(4)) such that the existence of a cyclic Gray code of {0, 1}(n) \ F for a given set F subset of {0, 1}(n) of size at most f(n) is NP-hard. In addition, we study the cases when the Gray code does not have to be cyclic, and moreover, when the first and the last vectors of the code are prescribed. For these two modifications, all NP-hardness and NP-completeness results hold as well. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Gray code Faulty vertex Hypercube Hamiltonian path Hamiltonian cycle NP-hard polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：