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

9th International Conference on Principles and Practice of Constraint Programming

作者： Chen, HB Univ Pompeu Fabra Dept Tecnol Barcelona Spain

We study a generalization of the constraint satisfaction problem (CSP), the periodic constraint satisfaction problem. An input instance of the periodic CSP is a finite set of "generating" constraints over a structured variable set that implicitly specifies a larger, possibly infinite set of constraints;the problem is to decide whether or not the larger set of constraints has a satisfying assignment. This model is natural for studying constraint networks consisting of constraints obeying a high degree of regularity or symmetry. Our main contribution is the identification of two broad polynomial-time tractable subclasses of the periodic CSP.

关键词： periodic problems polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Bribery and Control in Stable Marriage 13th

Bribery and Control in Stable Marriage

引用

13th International Symposium on Algorithmic Game Theory (SAGT)

作者： Boehmer, Niclas Bredereck, Robert Heeger, Klaus Niedermeier, Rolf TU Berlin Algorithm & Computat Complex Berlin Germany

ISBN: (纸本)9783030579807;9783030579791

We initiate the study of external manipulations in STABLE MARRIAGE by considering several manipulative actions as well as several "desirable" manipulation goals. For instance, one goal is to make sure that a given pair of agents is matched in a stable solution, and this may be achieved by the manipulative action of reordering some agents' preference lists. We present a comprehensive study of the computational complexity of all problems arising in this way. We find several polynomial-time solvable cases as well as NP-hard ones. For the NP-hard cases, focusing on the natural parameter "budget" (that is, the number of manipulative actions), we also perform a parameterized complexity analysis and encounter parameterized hardness results.

关键词： Stable matching Matching markets Manipulation Strategic behavior polynomial-time algorithms Parameterized hardness

来源：评论

学校读者我要写书评

暂无评论

On polynomial-time solvable linear diophantine problems

引用

Moscow Journal of Combinatorics and Number Theory 2019年第4期8卷 357-365页

作者： Aliev, Iskander Mathematics Institute Cardiff University Cardiff United Kingdom

We obtain a polynomial-time algorithm that, given input (A, b), where A = (B | N) ∈ ℤm ×n, m m ×m and b ∈ ℤm, finds a nonnegative integer solution to the system Ax = b or determines that no such solution e... 详细信息

We obtain a polynomial-time algorithm that, given input (A, b), where A = (B | N) ∈ ℤ^m ^×n, m < n, with nonsingular B ∈ ℤ^m ^×m and b ∈ ℤ^m, finds a nonnegative integer solution to the system Ax = b or determines that no such solution exists, provided that b is located sufficiently “deep” in the cone generated by the columns of B. This result improves on some of the previously known conditions that guarantee polynomial-time solvability of linear Diophantine problems. © 2019, Mathematical Sciences Publishers. All rights reserved.

关键词： Asymptotic integer programming Frobenius numbers Lattice points Multidimensional knapsack problem polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Strongly Stable and Maximum Weakly Stable Noncrossing Matchings 31st

Strongly Stable and Maximum Weakly Stable Noncrossing Matchi...

引用

31st International Workshop on Combinatorial algorithms (IWOCA)

作者： Hamada, Koki Miyazaki, Shuichi Okamoto, Kazuya NTT Corp 3-9-11 Midori Cho Musashino Tokyo 1808585 Japan Kyoto Univ Grad Sch Informat Sakyo Ku Yoshida Honmachi Kyoto 6068501 Japan Kyoto Univ Acad Ctr Comp & Media Studies Sakyo Ku Yoshida Honmachi Kyoto 6068501 Japan Kyoto Univ Hosp Div Med Informat Technol & Adm Planning Sakyo Ku 54 Kawaharacho Kyoto 6068507 Japan

ISBN: (纸本)9783030489656;9783030489663

In IWOCA 2019, Ruangwises and Itoh introduced stable noncrossing matchings, where participants of each side are aligned on each of two parallel lines, and no two matching edges are allowed to cross each other. They defined two stability notions, strongly stable noncrossing matching (SSNM) and weakly stable noncrossing matching (WSNM), depending on the strength of blocking pairs. They proved that a WSNM always exists and presented an O(n(2))-time algorithm to find one for an instance with n men and n women. They also posed open questions of the complexities of determining existence of an SSNM and finding a largest WSNM. In this paper, we show that both problems are solvable in polynomial time. Our algorithms are applicable to extensions where preference lists may include ties, except for one case which we show to be NP-complete.

关键词： Stable marriage Noncrossing matching polynomial-time algorithms NP-completeness

来源：评论

学校读者我要写书评

暂无评论

Semi-Definite Programming for Statistical Estimation: Power and Limitations

Semi-Definite Programming for Statistical Estimation: Power ...

引用

作者： Venkat, Prayaag Harvard University

学位级别：Ph.D., Doctor of Philosophy

The goal of this thesis to contribute towards a computational complexity theory of statistical inference problems. In recent years, researchers have built evidence in favor of an emerging hypothesis that the class of semi-definite programming (SDP) algorithms is optimal among for computationally efficient algorithms for a certain family of estimation problems. In this thesis, we present four main research efforts that refine this hypothesis and initiate preliminary efforts to go beyond it: • Optimal algorithms for private and robust estimation: We give the first polynomial-time algorithms for privately and robustly estimating a Gaussian distribution with optimal dependence on the dimension in the sample complexity. This adds the fundamental problem of private statistical estimation to a growing list of problems for which SDPs are optimal among polynomial-time algorithms. • Limitations of SDPs: Given independent standard Gaussian points in dimension d, for what values of (n, d) does there exist with high probability an origin-symmetric ellipsoid that simultaneously passes through all of the points? Based on strong numerical evidence, it was conjectured that the ellipsoid fitting problem transitions from feasible to infeasible as the number of points n increases, with a sharp threshold at n ∼ d 2/4; we resolve this conjecture up to logarithmic factors. A corollary of this result is that a canonical SDP-based algorithm fails to successfully solve inference problems involving low-rank matrix decompositions, independent component analysis, and principal component analysis. • New algorithms for discrepancy certification: We initiate the study of the algorithmic problem of certifying lower bounds on the discrepancy of random matrices, which has connections to conjecturally-hard average-case problems such as negatively-spiked PCA, the number-balancing problem and refuting random constraint satisfaction problems. We give the first polynomial-time algorithms with non-trivial

关键词： Computational complexity Semi-definite programming polynomial-time algorithms Practical algorithms Gaussian distribution

来源：评论

学校读者我要写书评

暂无评论

On the consistency of orthology relationships

On the consistency of orthology relationships

引用

14th Annual Research in Computational Molecular Biology (RECOMB) Comparative Genomics Satellite Workshop - Bioinformatics

作者： Jones, Mark Paul, Christophe Scornavacca, Celine Univ Montpellier CNRS LIRMM Montpellier France Univ Montpellier EPHE CNRS ISE MIRD Montpellier France

Background: Orthologs inference is the starting point of most comparative genomics studies, and a plethora of methods have been designed in the last decade to address this challenging task. In this paper we focus on the problems of deciding consistency with a species tree (known or not) of a partial set of orthology/paralogy relationships C on a collection of n genes. Results: We give the first polynomial algorithm - more precisely a O(n(3)) time algorithm - to decide whether C is consistent, even when the species tree is unknown. We also investigate a biologically meaningful optimization version of these problems, in which we wish to minimize the number of duplication events;unfortunately, we show that all these optimization problems are NP-hard and are unlikely to have good polynomial time approximation algorithms. Conclusions: Our polynomial algorithm for checking consistency has been implemented in Python and is available at https://***/UdeM-LBIT/OrthoPara-ConstraintChecker.

关键词： Orthology detection polynomial-time algorithms Para-NP hardness Inapproximability

来源：评论

学校读者我要写书评

暂无评论

Reconfiguring k-Path Vertex Covers

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2022年第7期E105D卷 1258-1272页

作者： Hoang, Duc A. Suzuki, Akira Yagita, Tsuyoshi Kyoto Univ Grad Sch Informat Kyoto 6068501 Japan Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan Kyushu Inst Technol Iizuka Fukuoka 8208502 Japan

A vertex subset I of a graph G is called a k-path vertex cover if every path on k vertices in G contains at least one vertex from I. The k-P ath V ertex C over R econfiguration (k-PVCR) problem asks if one can transform one k-path vertex cover into another via a sequence of kpath vertex covers where each intermediate member is obtained from its predecessor by applying a given reconfiguration rule exactly once. We investigate the computational complexity of k-PVCR from the viewpoint of graph classes under the well-known reconfiguration rules: TS, TJ, and TAR. The problem for k = 2, known as the Vertex Cover Reconfiguration (VCR) problem, has been well-studied in the literature. We show that certain known hardness results for VCR on different graph classes can be extended for k-PVCR. In particular, we prove a complexity dichotomy for k-PVCR on general graphs: on those whose maximum degree is three (and even planar), the problem is PSPACE-complete, while on those whose maximum degree is two (i.e., paths and cycles), the problem can be solved in polynomial time. Additionally, we also design polynomial-time algorithms for k-PVCR on trees under each of TJ and TAR. Moreover, on paths, cycles, and trees, we describe how one can construct a reconfiguration sequence between two given k-path vertex covers in a yes-instance. In particular, on paths, our constructed reconfiguration sequence is shortest.

关键词： combinatorial reconfiguration computational complexity k-path vertex cover PSPACE-completeness polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

polynomial-time Solvability of Dynamic Lot Size Problems

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2016年第3期33卷 1650018-1650018页

作者： Li, Chung-Lun Li, Qingying Hong Kong Polytech Univ Dept Logist & Maritime Studies Logist Management Kowloon Hong Kong Peoples R China Donghua Univ Glorious Sun Sch Business & Management 1882 West Yanan Rd Shanghai 200051 Peoples R China

There has been a lot of research on dynamic lot sizing problems with different nonlinear cost structures due to capacitated production, minimum order quantity requirements, availability of quantity discounts, etc. Developing optimal solutions efficiently for dynamic lot sizing models with nonlinear cost functions is a challenging topic. In this paper, we present a set of sufficient conditions such that if a single-item dynamic lot sizing problem satisfies these conditions, then the existence of a polynomial-time solution method for the problem is guaranteed. Several examples are presented to demonstrate the use of these sufficient conditions.

关键词： Inventory dynamic lot sizing dynamic programming polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

RECOGNIZING CIRCLE GRAPHS IN polynomial-time

引用

JOURNAL OF THE ACM 1989年第3期36卷 435-473页

作者： GABOR, CP SUPOWIT, KJ HSU, WL NORTHWESTERN UNIV EVANSTONIL 60201

The main result of this paper is an 0([V] x [E]) time algorithm for deciding whether a given graph is a circle graph, that is, the intersection graph of a set of chords on a circle. The algorithm utilizes two new graph-theoretic results, regarding necessary induced subgraphs of graphs having neither articulation points nor similar pairs of vertices. Furthermore, as a substep of the algorithm, it is shown how to find in 0([V] x [E]) time a decomposition of a graph into prime graphs, thereby improving on a result of Cunningham.

关键词： Circle graph graph decomposition induced subgraph intersection graph polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Stable roommates with narcissistic, single-peaked, and single-crossing preferences

引用

AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS 2020年第2期34卷 53-53页

作者： Bredereck, Robert Chen, Jiehua Finnendahl, Ugo Paavo Niedermeier, Rolf TU Berlin Berlin Germany TU Wien Vienna Austria

The classicalStable Roommatesproblem is to decide whether there exists a matching of an even number of agents such that no two agents which are not matched to each other would prefer to be with each other rather than with their respectively assigned partners. We investigateStable Roommateswith complete (i.e., every agent can be matched with any other agent) or incomplete preferences, with ties (i.e., two agents are considered of equal value to some agent) or without ties. It is known that in general allowing ties makes the problem NP-complete. We provide algorithms forStable Roommatesthat are, compared to those in the literature, more efficient when the input preferences are complete and have some structural property, such as being narcissistic, single-peaked, and single-crossing. However, when the preferences are incomplete and have ties, we show that being single-peaked and single-crossing does not reduce the computational complexity-Stable Roommatesremains NP-complete.

关键词： Stable matching Incomplete preferences Preferences with ties Restricted preference domains NP-completeness polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：