NSTL国家科技图书文献中心

1. CLUSTER BEFORE YOU HALLUCINATE: NODE-CAPACITATED NETWORK DESIGN AND ENERGY EFFICIENT ROUTING NSTL国家科技图书文献中心

Krishnaswamy, Ravish... | Nagarajan, Viswanath ... - 《SIAM Journal on Computing》 - 2024,53(3) - 588～623 - 共36页

摘要：We consider the following node-capacitated | network design problem. The input is an undirected graph | , a set of demands, uniform node capacity, and | arbitrary node costs. The goal is to find a minimum node | -cost subgraph that supports all demands concurrently

关键词： network design | approximation algorithms | routing | APPROXIMATION ALGORITHM | FLOW | HARDNESS | TREES

2. ECONOMICAL CONVEX COVERINGS AND APPLICATIONS NSTL国家科技图书文献中心

Arya, Sunil | da Fonseca, Guilherm...... - 《SIAM Journal on Computing》 - 2024,53(4) - 1002～1038 - 共37页

摘要：Coverings of convex bodies have emerged as a | central component in the design of efficient solutions | to approximation problems involving convex bodies | . Intuitively, given a convex body K and epsilon > 0, a | covering is a collection of convex bodies whose union

关键词： approximation algorithms | high dimensional geometry | convex coverings | Banach- Mazur metric | lattice algorithms | closest vector problem

3. 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

4. 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

5. 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

6. 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...

7. 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

8. 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

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

摘要：We consider the following node-capacitated | network design problem. The input is an undirected graph | , a set of demands, uniform node capacity, and | arbitrary node costs. The goal is to find a minimum node | -cost subgraph that supports all demands concurrently

关键词： network design | approximation algorithms | routing | APPROXIMATION ALGORITHM | FLOW | HARDNESS | TREES

摘要：Coverings of convex bodies have emerged as a | central component in the design of efficient solutions | to approximation problems involving convex bodies | . Intuitively, given a convex body K and epsilon > 0, a | covering is a collection of convex bodies whose union

关键词： approximation algorithms | high dimensional geometry | convex coverings | Banach- Mazur metric | lattice algorithms | closest vector problem

摘要：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

摘要：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

摘要：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

摘要：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...

摘要：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

摘要：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

摘要：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

摘要：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

4008-161-200 800-990-8900

国家科技图书文献中心