NSTL国家科技图书文献中心

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