搜索结果: 1-4 共查到“数学 Hardness”相关记录4条 . 查询时间(0.093 秒)
Academy of Mathematics and Systems Science, CAS Colloquia & Seminars：Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation Scheme
潘多拉盒问题 非强制性检查 硬度 近似方案
2023/4/14
Weitzman (1979) introduced the Pandora Box problem as a model for sequential search with inspection costs, and gave an elegant index-based policy that attains provably optimal expected payoff. In vari...
NP-hardness of Deciding Convexity of Quartic Polynomials and Related Problems
NP-hardness of Deciding Convexity of Quartic Polynomials Related Problems
2011/1/19
We show that unless P=NP, there exists no polynomial time (or even pseudo-polynomial time)
algorithm that can decide whether a multivariate polynomial of degree four (or higher even
degree) is globa...
Hardness, approximability, and exact algorithms for vector domination and total vector domination in graphs
Hardness approximability exact algorithms vector domination total vector domination
2011/3/2
We consider two graph optimization problems called vector domination and total vector domination. In vector domination one seeks a small subset S of vertices of a graph such that any vertex outside S ...
Hardness of k-Vertex-Connected Subgraph Augmentation Problem
Network survivability Graph connectivity
2012/12/3
Given a k-connected graph G = (V ,E) and V 伡 V , k-Vertex-Connected Subgraph Augmentation Problem (k-VCSAP) is to find S 伡 V \ V with minimum
cardinality such that the subgraph induced by V 伨 S ...