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

1. AN O (log log m ) PROPHET INEQUALITY FOR SUBADDITIVE COMBINATORIAL AUCTIONS NSTL国家科技图书文献中心

Duetting, Paul |  Kesselheim, Thomas... -  《SIAM Journal on Computing》 - 2024,53(6) - OCS20239~OCS20275 - 共37页 - 被引量:1

摘要:Prophet inequalities compare the expected |  performance of an online algorithm for a stochastic |  optimization problem to the expected optimal solution in |  hindsight. They are a major alternative to classic worst | -case competitive analysis, of particular importance
关键词: prophet inequality |  posted prices |  combinatorial auction |  mechanism design

2. ON THE PRIVACY OF NOISY STOCHASTIC GRADIENT DESCENT FOR CONVEX OPTIMIZATION NSTL国家科技图书文献中心

Altschuler, Jason M. |  Bok, Jinho... -  《SIAM Journal on Computing》 - 2024,53(4) - 969~1001 - 共33页

摘要:A central issue in machine learning is how to |  train models on sensitive user data. Industry has |  widely adopted a simple algorithm: Stochastic Gradient |  Descent (SGD) with noise (a.k.a. algorithm's privacy |  loss remain open---even in the seemingly simple
关键词: differential privacy |  convex optimization |  noisy stochastic gradient descent |  stochastic gradient Langevin dynamics |  privacy amplification by iteration |  shifted divergences

3. REVISIONIST SIMULATIONS: A NEW APPROACH TO PROVING SPACE LOWER BOUNDS NSTL国家科技图书文献中心

Ellen, Faith |  Gelashvili, Rati... -  《SIAM Journal on Computing》 - 2024,53(4) - 1039~1084 - 共46页

摘要:Determining the number of registers required |  for solving obstruction-free (or randomized wait | -free) k-set agreement is an open problem that |  highlights important gaps in our understanding of the space |  complexity of synchronization. The best known upper bound
关键词: distributed computing |  space complexity |  consensus |  set agreement |  lower bounds |  shared memory

4. ALGORITHMS FOR SUBPATH CONVEX HULL QUERIES AND RAY-SHOOTING AMONG SEGMENTS NSTL国家科技图书文献中心

Wang, Haitao -  《SIAM Journal on Computing》 - 2024,53(4) - 1132~1161 - 共30页

摘要:In this paper, we first consider the subpath |  convex hull query problem: Given a simple path pi of n |  vertices, preprocess it so that the convex hull of any |  query subpath of pi can be quickly obtained | . Previously, Guibas, Hershberger, and Snoeyink [Int. J
关键词: subpath hull queries |  convex hulls |  compact interval trees |  ray-shooting

5. COUNTING SMALL INDUCED SUBGRAPHS WITH HEREDITARY PROPERTIES NSTL国家科技图书文献中心

Focke, Jacob |  Roth, Marc -  《SIAM Journal on Computing》 - 2024,53(2) - 189~220 - 共32页

摘要:We study the computational complexity of the |  problem #INDSUB(Phi ) of counting k -vertex induced |  subgraphs of a graph G that satisfy a graph property Phi |  . Our main result establishes an exhaustive and |  explicit classification for all hereditary properties
关键词: counting complexity |  parameterized complexity |  induced subgraphs |  hereditary properties |  fine-grained complexity |  graph homomorphisms |  PARAMETERIZED COMPLEXITY |  LOWER BOUNDS |  STATISTICS |  DISCOVERY...

6. FAST FPT-APPROXIMATION OF BRANCHWIDTH NSTL国家科技图书文献中心

Fomin, Fedor, V |  Korhonen, Tuukka -  《SIAM Journal on Computing》 - 2024,53(4) - 1085~1131 - 共47页

摘要:Branchwidth determines how graphs and, more |  generally, arbitrary connectivity (symmetric and |  submodular) functions can be decomposed into a tree-like |  structure by specific cuts. We develop a general framework |  for designing fixed-parameter tractable 2
关键词: branchwidth |  rankwidth |  cliquewidth |  graph algorithms |  parameterized algorithms |  approximation algorithms

7. PTAS FOR MINIMUM COST MULTICOVERING WITH DISKS NSTL国家科技图书文献中心

Huang, Ziyun |  Feng, Qilong... -  《SIAM Journal on Computing》 - 2024,53(4) - 1181~1215 - 共35页

摘要:In this paper, we study the following Minimum |  Cost Multicovering (MCMC) problem: Given a set of n |  client points C and a set of m server points S in a |  fixed dimensional Rd space, determine a set of disks |  centered at these server points so that each client point
关键词: minimum cost multi-covering |  geometric set cover |  PTAS |  approximation algorithms |  computational geometry

8. FURTHER COLLAPSES IN TFNP NSTL国家科技图书文献中心

Goos, Mika |  Hollender, Alexandro...... -  《SIAM Journal on Computing》 - 2024,53(3) - 573~587 - 共15页

摘要:We show EOPL = PLS cap PsansP sansP AD. Here |  the class EOPL consists of all total search problems |  that reduce to the END -OF -POTENTIAL -LINE problem | , which was introduced in the works by Hub'acv ek and |  Yogev (SICOMP 2020) and Fearnley et al. (JCSS 2020
关键词: TFNP |  PLS |  PPAD |  EOPL |  PARITY ARGUMENT |  COMPLEXITY

9. UNIT CAPACITY MAXFLOW IN ALMOST m 4 / TIME NSTL国家科技图书文献中心

Kathuria, Tarun |  Liu, Yang P.... -  《SIAM Journal on Computing》 - 2024,53(6) - OCS20175~OCS20204 - 共30页 - 被引量:1

摘要:We present an algorithm which given any m | - edge directed graph with positive integer capacities |  at most U, vertices a and b, and an approximation |  parameter epsilon in (0, 1) computes an additive epsilonmU | -approximate a-b maximum flow in time m1+o(1)/surdepsilon. By
关键词: maximum flow |  optimization |  interior point methods

10. COLLAPSING THE BOUNDED WIDTH HIERARCHY FOR INFINITE-DOMAIN CONSTRAINT SATISFACTION PROBLEMS: WHEN SYMMETRIES ARE ENOUGH NSTL国家科技图书文献中心

Mottet, Antoine |  Nagy, Tomas... -  《SIAM Journal on Computing》 - 2024,53(6) - 1709~1745 - 共37页

摘要:We prove that relational structures admitting |  specific polymorphisms (namely, canonical pseudo-WNU |  operations of all arities n geq 3) have low relational |  width. This implies a collapse of the bounded width |  hierarchy for numerous classes of infinite-domain
关键词: local consistency |  bounded width |  constraint satisfaction problems |  polymorphisms |  smooth approximations
检索条件出处:SIAM Journal on Computing

NSTL主题词

  • NSTL学科导航