全部 |
  • 全部
  • 题名
  • 作者
  • 机构
  • 关键词
  • NSTL主题词
  • 摘要
检索 二次检索 AI检索
外文文献 中文文献
筛选条件:

1. Approximation hardness of domination problems on generalized convex graphs NSTL国家科技图书文献中心

Wang, Po Yuan |  Kitamura, Naoki... -  《Theoretical computer science》 - 2025,1028 - 共12页

摘要: subclasses. This study examines the approximation hardness |  convex bipartite graphs. We explore the approximation |  hardness for various domination problem variants |  unbounded t or O results in APX-hardness for all examined | The domination problem and its variants in
关键词: Domination problem |  Tree convex bipartite graph |  Approximation hardness |  Generalized convex graph

2. Finer-grained reductions in fine-grained hardness of approximation NSTL国家科技图书文献中心

Abboud, Elie |  Ron-Zewi, Noga -  《Theoretical computer science》 - 2025,1026 - 共12页

摘要: approximation. Our reduction combines the hardness of |  required for obtaining a (1 + S)-approximation in time N | )-approximation algorithm for (bichromatic) Euclidean Closest |  (1 +S)-approximation algorithm exists for Euclidean |  the approximation guarantee of S e3 for Euclidean
关键词: ALGORITHM |  COMPLEXITY

3. On penalized reload cost path, walk, tour and maximum flow: hardness and approximation NSTL国家科技图书文献中心

Granata, Donatella -  《Optimization Letters》 - 2025,19(1) - 123~138 - 共16页

摘要:A meticulous description of a real network |  with respect to its heterogeneous physical |  infrastructure and properties is necessary for network design |  assessment. Quantifying the costs of making these |  structures work together effectively, and taking into
关键词: Reload cost |  Approximability |  NP-completeness |  Penalized reload cost |  Network design

4. Efficient Approximation of the CREM Gibbs Measure and the Hardness Threshold NSTL国家科技图书文献中心

Ho, Fu-Hsuan -  《Journal of Statistical Physics》 - 2025,192(3) - 共33页

摘要: exhibits a threshold beta(G) beta(G) , a hardness result | The continuous random energy model (CREM) is a |  toy model of disordered systems introduced by Bovier |  and Kurkova in 2004 based on previous work by |  Derrida and Spohn in the 80s. In a recent paper by
关键词: Algorithmic hardness |  Continuous random energy model |  Gaussian process |  Gibbs measure |  Kullback-Leibler divergence |  Spin glass

5. Affine optimal k -proper connected edge colorings NSTL国家科技图书文献中心

Barish, Robert D. |  Shibuya, Tetsuo -  《Optimization Letters》 - 2025,19(1) - 151~168 - 共18页

摘要: randomized approximation scheme can exist for approximating | We introduce affine optimal k-proper connected |  edge colorings as a variation on Fujita's notion of |  optimal k-proper connected colorings (Fujita in Optim |  Lett 14(6):1371-1380, 2020. https://doi.org/10.1007
关键词: Optimal proper connection number |  Proper connection |  Edge coloring |  Optimization hardness |  Approximation hardness |  FPRAS

6. Hardness of Approximate Diameter: Now for Undirected Graphs NSTL国家科技图书文献中心

MINA DALIRROOYFARD |  RAY LI... -  《Journal of the ACM》 - 2025,72(1) - 6.1~6.32 - 共32页

摘要: simple folklore algorithm can output a 2-approximation |  better approximation is possible in near-linear time. A |  to strong hardness results for diameter in directed |  > 0, a 2 1 k approximation for diameter in |  particular, the simple linear time 2-approximation
关键词: Fine-grained complexity |  hardness of approximation |  graph diameter |  undirected graphs

7. On approximating partial scenario set cover NSTL国家科技图书文献中心

Dimant, Shai Michael |  Krumke, Sven O. -  《Theoretical computer science》 - 2025,1023 - 共18页

摘要:. We present two approximation approaches. The first |  approximation for the general case, which we use as a |  approximation for PSSC. | The Partial Scenario Set Cover problem (PSSC | ) generalizes the Partial Set Cover problem, which is itself a
关键词: Combinatorial optimization |  Set cover |  Partial cover |  Approximation algorithm |  NP-hardness

8. Tight bounds for budgeted maximum weight independent set in bipartite and perfect graphs NSTL国家科技图书文献中心

Doron-Arad, Ilan |  Shachnai, Hadas -  《Discrete Applied Mathematics》 - 2025,361 - 453~464 - 共12页

摘要: work, the best possible approximation guarantees for |  tight 2-approximation for BMWIS on perfect graphs and | -approximation for BMWIS on perfect graphs using a Lagrangian |  approximation scheme (EPTAS). Thus, the existing PTAS for | We consider the classic budgeted maximum
关键词: Maximum independent set |  Budgeted constrained maximization |  Bipartite graph |  Perfect graph |  Hardness of approximation

9. Investigation and Comparison of Structural, Electronic and Thermodynamic Properties of Lanthanum Carbide Compound using GGA and LDA Approximation NSTL国家科技图书文献中心

Aqeel, A. |  Khajehnezhad, A.... -  《Transactions of the Indian Institute of Metals》 - 2025,78(3) - 72~ - 共7页

摘要: GGA approximation, it leads to increase in hardness |  calculations are mainly done in local density approximation |  (LDA) and generalized gradient approximation (GGA) in |  compound is harder in LDA approximation in comparison |  parameter is smaller in LDA approximation with respect to
关键词: Density functional theory |  Lanthanum carbide |  Thermodynamic properties |  Dynamic properties |  Structural stability |  Optical band gap

10. The complexity of ferromagnetic 2-spin systems on bounded degree graphs NSTL国家科技图书文献中心

Bai, Zonglei |  Cao, Yongzhi... -  《Theoretical computer science》 - 2025,1028 - 共16页

摘要: polynomial time approximation scheme (FPTAS) for the |  hardness side, we prove the # BIS-hardness of | Spin systems model the interactions between |  neighbors on graphs. An important special case is when |  there are only 2-spins. For 2-spin systems, the
关键词: Spin systems |  Approximate counting |  Zeros |  FPTAS |  Phase transition
检索条件Approximation hardness

NSTL主题词

  • NSTL学科导航