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

Wasserstein Barycenters can be Computed in polynomial time in Fixed Dimension

JOURNAL OF MACHINE LEARNING RESEARCH 2021年第1期22卷 1-19页

作者： Altschuler, Jason M. Boix-Adsera, Enric MIT Lab Informat & Decis Syst 77 Massachusetts Ave Cambridge MA 02139 USA

Computing Wasserstein barycenters is a fundamental geometric problem with widespread applications in machine learning, statistics, and computer graphics. However, it is unknown whether Wasserstein barycenters can be computed in polynomial time, either exactly or to high precision (i.e., with polylog(1/epsilon) runtime dependence). This paper answers these questions in the affirmative for any fixed dimension. Our approach is to solve an exponential-size linear programming formulation by efficiently implementing the corresponding separation oracle using techniques from computational geometry.

关键词： Wasserstein barycenters free support polynomial-time algorithm exponential-size linear program power diagrams

来源：评论

学校读者我要写书评

暂无评论

A linear-time algorithm for semitotal domination in strongly chordal graphs

引用

DISCRETE APPLIED MATHEMATICS 2023年第1期338卷 77-88页

作者： Tripathi, Vikash Pandey, Arti Maheshwari, Anil Indian Inst Technol Ropar Dept Math Ropar Punjab India Carleton Univ Sch Comp Sci Ottawa ON Canada

In a graph, G = (V, E) without an isolated vertex, a dominating set D & SUBE;V, is called a semitotal dominating set if for every vertex u & ISIN;D there is another vertex v & ISIN;D such that distance between u and v is at most two in G. Given a graph G = (V, E) without an isolated vertex, the MINIMUM SEMITOTAL DOMINATION problem is to find a minimum cardinality semitotal dominating set of G. The semitotal domination number, denoted by & gamma;t2(G), is the minimum cardinality of a semitotal dominating set of G. It is known that the decision version of the problem remains NP-complete even when restricted to chordal graphs, chordal bipartite graphs, and planar graphs. Galby et al. (2020) proved that the problem can be solved in polynomial time for bounded MIMwidth graphs, which include many well known graph classes, but left the complexity of the problem in strongly chordal graphs unresolved. Henning and Pandey (2019) also asked to resolve the complexity status of the problem in strongly chordal graphs. In this paper, we resolve the complexity of the problem in strongly chordal graphs by designing a linear-time algorithm for the problem.& COPY;2023 Elsevier B.V. All rights reserved.

关键词： Domination Total domination Semitotal domination Strongly chordal graphs polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Weighted Triangle-free 2-matching Problem with Edge-disjoint Forbidden Triangles

引用

MATHEMATICAL PROGRAMMING 2022年第1-2期192卷 675-702页

作者： Kobayashi, Yusuke Kyoto Univ Res Inst Math Sci Kyoto 6068502 Japan

The weighted T-free 2-matching problem is the following problem: given an undirected graph G, a weight function on its edge set, and a set T of triangles in G, find a maximum weight 2-matching containing no triangle in T. When T is the set of all triangles in G, this problem is known as the weighted triangle-free 2-matching problem, which is a long-standing open problem. A main contribution of this paper is to give the first polynomial-time algorithm for the weighted T-free 2-matching problem under the assumption that T is a set of edge-disjoint triangles. In our algorithm, a key ingredient is to give an extended formulation representing the solution set, that is, we introduce new variables and represent the convex hull of the feasible solutions as a projection of another polytope in a higher dimensional space. Although our extended formulation has exponentially many inequalities, we show that the separation problem can be solved in polynomial time, which leads to a polynomial-time algorithm for the weighted T-free 2-matching problem.

关键词： Restricted 2-matching polynomial-time algorithm Triangle-free Extended formulation

来源：评论

学校读者我要写书评

暂无评论

Maximizing the strong triadic closure in split graphs and proper interval graphs

引用

DISCRETE APPLIED MATHEMATICS 2020年 285卷 79-95页

作者： Konstantinidis, Athanasios L. Papadopoulos, Charis Univ Ioannina Dept Math Ioannina Greece

In social networks the STRONG TRIADIC CLOSURE is an assignment of the edges with strong or weak labels such that any two vertices that have a common neighbor with a strong edge are adjacent. The problem of maximizing the number of strong edges that satisfy the strong triadic closure was recently shown to be NP-complete for general graphs. Here we initiate the study of graph classes for which the problem is solvable. We show that the problem admits a polynomial-time algorithm for two incomparable classes of graphs: proper interval graphs and trivially-perfect graphs. To complement our result, we show that the problem remains NP-complete on split graphs, and consequently also on chordal graphs. Thus, we contribute to define the first border between graph classes on which the problem is polynomially solvable and on which it remains NP-complete. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Strong triadic closure polynomial-time algorithm NP-completeness Split graphs Proper interval graphs

来源：评论

学校读者我要写书评

暂无评论

Scheduling imprecise computation tasks with 0/1-constraint

引用

DISCRETE APPLIED MATHEMATICS 1997年第1-3期78卷 117-132页

作者： Ho, KIJ Leung, JYT Wei, WD Department of Computer Science and Engineering University of Nebraska-Lincoln Lincoln NE 68588-0115 USA

We consider the problem of preemptively scheduling a set of imprecise computation tasks on a single processor, with the added constraint that each optional subtask is either fully executed or entirely discarded. Two performance metrics are considered: (1) the total error;(2) the number of imprecisely scheduled tasks (i.e., tasks whose optional subtasks are entirely discarded). Since the problem of minimizing the total error is NP-hard, we consider an O(n(2))-time heuristic for it, where n is the number of tasks. It is shown that the total error of the schedule produced by the heuristic is at most three times that of an optimal schedule and the bound is tight. For the problem of minimizing the number of imprecisely scheduled tasks, we show that it can be solved in O(n(5)) time. Since the time complexity is unacceptably high, we consider an O(n(2))-time heuristic for it. It is shown that the number of imprecisely scheduled tasks in the schedule produced by the heuristic is at most twice that in an optimal schedule and the bound is tight. Interestingly, the number of precisely scheduled tasks (i.e., tasks whose optional subtasks are fully executed) in an optimal schedule is also at most twice that in the schedule produced by the heuristic and the bound is tight.

关键词： real-time system imprecise computation task single processor preemptive scheduling NP-hard polynomial-time algorithm heuristics worst-case analysis

来源：评论

学校读者我要写书评

暂无评论

Robotic-cell scheduling: Special polynomially solvable cases of the traveling salesman problem on permuted Monge matrices

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2005年第4期9卷 381-399页

作者： Deineko, VG Steiner, G Xue, ZH Univ Warwick Warwick Business Sch Coventry CV4 7AL W Midlands England McMaster Univ DeGroote Sch Business Hamilton ON L8S 4M4 Canada

In this paper, we introduce the 1 - K robotic-cell scheduling problem, whose solution can be reduced to solving a TSP on specially structured permuted Monge matrices, we call b-decomposable matrices. We also review a number of other scheduling problems which all reduce to solving TSP-s on permuted Monge matrices. We present the important insight that the TSP on b-decomposable matrices can be solved in polynomial time by a special adaptation of the well-known subtour-patching technique. We discuss efficient implementations of this algorithm on newly defined subclasses of permuted Monge matrices.

关键词： robotic-cell scheduling traveling salesman problem permuted Monge matrix polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

The Implication Problem for Functional Dependencies and Variants of Marginal Distribution Equivalences

引用

ACM TRANSACTIONS ON COMPUTATIONAL LOGIC 2024年第4期25卷 1-23页

作者： Hirvonen, Minna Univ Helsinki Helsinki Finland

We study functional dependencies together with two different probabilistic dependency notions: unary marginal identity and unary marginal distribution equivalence. A unary marginal identity states that two variables x and y are identically distributed. A unary marginal distribution equivalence states that the multiset consisting of the marginal probabilities of all the values for variable x is the same as the corresponding multiset for y . We present a sound and complete axiomatization for the class of these dependencies and show that it has Armstrong relations. The axiomatization is infinite, but we show that there can be no finite axiomatization. The implication problem for the subclass that contains only functional dependencies and unary marginal identities can be simulated with functional dependencies and unary inclusion atoms, and therefore the problem is in polynomial-time. This complexity bound also holds in the case of the full class, which we show by constructing a polynomial-time algorithm.

关键词： Armstrong relations complete axiomatization functional dependency inclusion dependency marginal distribution equivalence polynomial-time algorithm probabilistic team semantics

来源：评论

学校读者我要写书评

暂无评论

A Generalized Polymatroid Approach to Stable Matchings with Lower Quotas

引用

MATHEMATICS OF OPERATIONS RESEARCH 2017年第1期42卷 238-255页

作者： Yokoi, Yu Univ Tokyo Dept Math Informat Tokyo 1138656 Japan

Classified stable matching, proposed by Huang, describes a matching model between academic institutes and applicants, in which each institute has upper and lower quotas on classes, i.e., subsets of applicants. Huang showed that the problem to decide whether there exists a stable matching or not is NP-hard in general. On the other hand, he showed that the problem is solvable if classes form a laminar family. For this case, Fleiner and Kamiyama gave a concise interpretation in terms of matroids and showed the lattice structure of stable matchings. In this paper we introduce stable matchings on generalized matroids, extending the model of Fleiner and Kamiyama. We design a polynomial-time algorithm which finds a stable matching or reports the nonexistence. We also show that the set of stable matchings, if nonempty, forms a lattice with several significant properties. Furthermore, we extend this structural result to the polyhedral framework, which we call stable allocations on generalized polymatroids.

关键词： stable matching lower quotas matroids generalized polymatroids polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Zero Duality Gap in Optimal Power Flow Problem

引用

IEEE TRANSACTIONS ON POWER SYSTEMS 2012年第1期27卷 92-107页

作者： Lavaei, Javad Low, Steven H. CALTECH Dept Control & Dynam Syst Pasadena CA 91125 USA CALTECH Dept Comp Sci & Elect Engn Pasadena CA 91125 USA

The optimal power flow (OPF) problem is nonconvex and generally hard to solve. In this paper, we propose a semidefinite programming (SDP) optimization, which is the dual of an equivalent form of the OPF problem. A global optimum solution to the OPF problem can be retrieved from a solution of this convex dual problem whenever the duality gap is zero. A necessary and sufficient condition is provided in this paper to guarantee the existence of no duality gap for the OPF problem. This condition is satisfied by the standard IEEE benchmark systems with 14, 30, 57, 118, and 300 buses as well as several randomly generated systems. Since this condition is hard to study, a sufficient zero-duality-gap condition is also derived. This sufficient condition holds for IEEE systems after small resistance (10(-5) per unit) is added to every transformer that originally assumes zero resistance. We investigate this sufficient condition and justify that it holds widely in practice. The main underlying reason for the successful convexification of the OPF problem can be traced back to the modeling of transformers and transmission lines as well as the non-negativity of physical quantities such as resistance and inductance.

关键词： Convex optimization linear matrix inequality optimal power flow polynomial-time algorithm power system

来源：评论

学校读者我要写书评

暂无评论

Maximum-cover source location problems with objective edge-connectivity three

引用

MATHEMATICAL METHODS OF OPERATIONS RESEARCH 2009年第1期70卷 183-193页

作者： Sugihara, Kenya Ito, Hiro Kyoto Univ Grad Sch Informat Sakyo Ku Kyoto 6068501 Japan

Given a graph G = (V, E), a set of vertices S subset of V covers a vertex v is an element of V if the edge-connectivity between S and v is at least a given number k. Vertices in S are called sources. The maximum-cover source location problem, which is a variation of the source location problem, is to find a source set S with a given size at most p, maximizing the sum of the weight of vertices covered by S. In this paper, we show a polynomial-time algorithm for this problem in the case of k = 3 for a given undirected graph with a vertex weight function and an edge capacity function. Moreover, we show that this problem is NP-hard even if vertex weights and edge capacities are both uniform for general k.

关键词： Maximum-cover source location problem polynomial-time algorithm NP-hard

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：