References:

@article{IW,
author = {Imase, Makoto and Waxman, Bernard M.},
title = {Dynamic Steiner Tree Problem},
journal = {SIAM Journal on Discrete Mathematics},
volume = {4},
number = {3},
pages = {369-384},
year = {1991},
doi = {10.1137/0404033},
URL = {https://doi.org/10.1137/0404033},
eprint = {https://doi.org/10.1137/0404033},
abstract = { This paper proposes a new problem called the dynamic Steiner tree problem. Interest in the dynamic Steiner tree problem is motivated by multipoint routing in communication networks, where the set of nodes in the connection changes over time. This problem, which has its basis in the Steiner tree problem on graphs, can be divided into two cases: one in which rearrangement of existing routes is not allowed, and a second in which rearrangement is allowed.For the nonrearrangeable version, it is shown that the worst-case performance for any algorithm is at least \$\frac{1}{2}\lg n\$ times the cost of an optimum solution with complete rearrangement. Here n is the maximum number of nodes to be connected. In addition, a simple, polynomial time algorithm is present that has worst-case performance within two times this bound. In the rearrangeable case, a polynomial time algorithm is presented with worst-case performance bounded by a constant times optimum. }
}

@inproceedings{AA,
author = {Alon, Noga and Azar, Yossi},
title = {On-line Steiner trees in the Euclidean plane},
year = {1992},
isbn = {0897915178},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/142675.142744},
doi = {10.1145/142675.142744},
abstract = {Suppose we are given a sequence of n points v1,…,vn in the Euclidean plane, and our objective is to construct, on-line, a connected graph that connects all of them, trying to minimize the total sum of lengths of its edges. We assume that the points appear one at a time, vi arriving at step i. At the end of step i, the on-line algorithm must construct a connected graph Ti-1. This can be done by joining vi (not necessarily by a straight line) to any point of Ti-1, which need not necessarily be one of the previously given points vj. The performance of our algorithm is measured by its competitive ratio: the supremum, over all sequences v1,…,vn as above, of the ratio between the total length of the graph constructed by our algorithm and the total length of the best Steiner tree that connects all the points v1,…, vn. There are known on-line algorithms whose competitive ratio is O(log n), but there is no known nontrivial lower bound for the best possible competitive ratio. Here we prove that the upper bound is almost tight by establishing an Ω(log n/log log n) lower bound for the competitive ratio of any on-line algorithm. The lower bound holds for deterministic algorithms as well as for randomized ones, and obviously holds in any Euclidean space of dimension greater than 2 as well.},
booktitle = {Proceedings of the Eighth Annual Symposium on Computational Geometry},
pages = {337–343},
numpages = {7},
location = {Berlin, Germany},
series = {SCG '92}
}

@inproceedings{BC,
author = {Berman, Piotr and Coulston, Chris},
title = {On-line algorithms for Steiner tree problems (extended abstract)},
year = {1997},
isbn = {0897918886},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/258533.258618},
doi = {10.1145/258533.258618},
booktitle = {Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing},
pages = {344–353},
numpages = {10},
location = {El Paso, Texas, USA},
series = {STOC '97}
}

@inproceedings{Aweretal,
author = {Awerbuch, Baruch and Azar, Yossi and Bartal, Yair},
title = {On-line generalized Steiner problem},
year = {1996},
isbn = {0898713668},
doi={10.5555/313852.313888},
publisher = {Society for Industrial and Applied Mathematics},
address = {USA},
booktitle = {Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms},
pages = {68–74},
numpages = {7},
location = {Atlanta, Georgia, USA},
series = {SODA '96}
}

@inproceedings{Gargetal,
author = {Garg, Naveen and Gupta, Anupam and Leonardi, Stefano and Sankowski, Piotr},
title = {Stochastic analyses for online combinatorial optimization problems},
year = {2008},
publisher = {Society for Industrial and Applied Mathematics},
address = {USA},
doi={10.5555/1347082.1347185},
abstract = {In this paper, we study online algorithms when the input is not chosen adversarially, but consists of draws from some given probability distribution. While this model has been studied for online problems like paging and k-server, it is not known how to beat the Φ(log n) bound for online Steiner tree if at each time instant, the demand vertex is a uniformly random vertex from the graph. For the online Steiner tree problem, we show that if each demand vertex is an independent draw from some probability distribution π: V → [0, 1], a variant of the natural greedy algorithm achieves Eω[A(ω)]/Eω[OPT (ω)] = O(1); moreover, this result can be extended to some other subadditive problems. Both assumptions that the input sequence consists of independent draws from π, and that π is known to the algorithm are both essential; we show (almost) logarithmic lower bounds if either assumption is violated. Moreover, we give preliminary results on extending the Steiner tree results above to the related "expected ratio" measure Eω[ω(ω)/OPT (ω)]. Finally, we use these ideas to give an average-case analysis of the Universal TSP problem.},
booktitle = {Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms},
pages = {942–951},
numpages = {10},
location = {San Francisco, California},
series = {SODA '08}
}


@inproceedings{Bamasetal,
title={An Improved Analysis of Greedy for Online Steiner Forest},
author={{\'E}tienne Bamas and Marina Drygala and Andreas Maggiori},
booktitle={ACM-SIAM Symposium on Discrete Algorithms},
year={2021},
url={https://api.semanticscholar.org/CorpusID:244463208}
}

@InProceedings{Barhum,
author="Barhum, Kfir",
editor="Geffert, Viliam
and Preneel, Bart
and Rovan, Branislav
and {\v{S}}tuller, J{\'u}lius
and Tjoa, A. Min",
title="Tight Bounds for the Advice Complexity of the Online Minimum Steiner Tree Problem",
booktitle="SOFSEM 2014: Theory and Practice of Computer Science",
year="2014",
publisher="Springer International Publishing",
address="Cham",
pages="77--88",
doi={10.1007/978-3-319-04298-5_8},
abstract="In this work, we study the advice complexity of the online minimum Steiner tree problem (ST). Given a (known) graph G{\thinspace}={\thinspace}(V,E) endowed with a weight function on the edges, a set of N terminals are revealed in a step-wise manner. The algorithm maintains a sub-graph of chosen edges, and at each stage, chooses more edges from G to its solution such that the terminals revealed so far are connected in it. In the standard online setting this problem was studied and a tight bound of O(log(N)) on its competitive ratio is known. Here, we study the power of non-uniform advice and fully characterize it. As a first result we show that using q {\textperiodcentered}log(|V|) advice bits, where 0{\thinspace}≤{\thinspace}q{\thinspace}≤{\thinspace}N{\thinspace}−{\thinspace}1, it is possible to obtain an algorithm with a competitive ratio of O(log(N/q). We then show a matching lower bound for all values of q, and thus settle the question.",
isbn="978-3-319-04298-5"
}

@book{Berge89,
title={Hypergraphs: Combinatorics of Finite Sets},
author={Claude Berge},
publisher={"North-Holland"},
year={1989},
url={https://api.semanticscholar.org/CorpusID:118462684}
}

@article{Ljubic,
title={Solving Steiner trees: Recent advances, challenges, and perspectives},
author={Ivana Ljubi{\'c}},
journal={Networks},
year={2020},
volume={77},
pages={177 - 204},
url={https://api.semanticscholar.org/CorpusID:229458488}
}

@misc{knuthwebsite,
author = "Donald Knuth",
title = "Knuth: Computers and Typesetting",
url = "http://www-cs-faculty.stanford.edu/\~{}uno/abcde.html"
}

@article{Zhaoetal,
author = {Zhao, Liang and Nagamochi, Hiroshi and Ibaraki, Toshihide},
year = {2003},
month = {03},
pages = {275-289},
title = {A primal–dual approximation algorithm for the survivable network design problem in hypergraphs},
volume = {126},
journal = {Discrete Applied Mathematics},
doi = {10.1016/S0166-218X(02)00201-9}
}

@inproceedings{GW,
author = {Goemans, Michel X. and Williamson, David P.},
title = {A general approximation technique for constrained forest problems},
year = {1992},
isbn = {089791466X},
publisher = {Society for Industrial and Applied Mathematics},
address = {USA},
abstract = {We present a general approximation technique for a large class of graph problems. Our technique mostly applies to problems of covering, at minimum cost, the vertices of a graph with trees, cycles or paths satisfying certain requirements. In particular, many basic combinatorial optimization problems fit in this framework, including the shortest path, minimum spanning tree, minimum-weight perfect matching, traveling salesman and Steiner tree problems.Our technique produces approximation algorithms that run in O(n2 log n) time and come within a factor of 2 of optimal for most of these problems. For instance, we obtain a 2-approximation algorithm for the minimum-weight perfect matching problem under the triangle inequality. Our running time of O(n2 log n) time compares favorably with the best strongly polynomial exact algorithms running in O(n3) time for dense graphs. A similar result is obtained for the 2-matching problem and its variants.We also derive the first approximation algorithms for many NP-complete problems, including the non-fixed point-to-point connection problem, the exact path partitioning problem and complex location-design problems. Moreover, for the prize-collecting traveling salesman or Steiner tree problems, we obtain 2-approximation algorithms, therefore improving the previously best-known performance guarantees of 2.5 and 3, respectively [4].},
booktitle = {Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms},
pages = {307–316},
numpages = {10},
location = {Orlando, Florida, USA},
series = {SODA '92},
doi={10.5555/139404.139468}
}

@article{HS,
title = {Steiner connectivity problems in hypergraphs},
journal = {Information Processing Letters},
volume = {183},
pages = {106428},
year = {2024},
issn = {0020-0190},
doi = {https://doi.org/10.1016/j.ipl.2023.106428},
url = {https://www.sciencedirect.com/science/article/pii/S0020019023000716},
author = {Florian Hörsch and Zoltán Szigeti},
keywords = {Steiner trees, Hypergraphs, Connectivity, Orientation, Computational complexity},
abstract = {We say that a tree T is an S-Steiner tree if S⊆V(T) and a hypergraph is an S-Steiner hypertree if it can be trimmed to an S-Steiner tree. We prove that it is NP-complete to decide, given a hypergraph H and some S⊆V(H), whether there is a subhypergraph of H which is an S-Steiner hypertree. As corollaries, we give two negative results for two Steiner orientation problems in hypergraphs. Firstly, we show that it is NP-complete to decide, given a hypergraph H, some r∈V(H) and some S⊆V(H), whether this hypergraph has an orientation in which every vertex of S is reachable from r. Secondly, we show that it is NP-complete to decide, given a hypergraph H and some S⊆V(H), whether this hypergraph has an orientation in which any two vertices in S are mutually reachable from each other. This answers a longstanding open question of the Egerváry Research group. We further show that it is NP-complete to decide if a given hypergraph has a well-balanced orientation. On the positive side, we show that the problem of finding a Steiner hypertree and the first orientation problem can be solved in polynomial time if the number of terminals |S| is fixed.}
}

@book{Bela,
author = {Bollobas, B\'{e}la},
title = {Extremal Graph Theory},
year = {2004},
isbn = {0486435962},
publisher = {Dover Publications, Inc.},
address = {USA}
}

@book{Dasgupta,
title={Algorithms},
author={Dasgupta, S. and Papadimitriou, C.H. and Vazirani, U.V.},
isbn={9780077388492},
url={https://books.google.ca/books?id=DJSUCgAAQBAJ},
year={2006},
publisher={McGraw-Hill Higher Education}
}

@book{Harary,
added-at = {2011-03-14T01:03:39.000+0100},
address = {Reading, MA},
author = {Harary, F.},
biburl = {https://www.bibsonomy.org/bibtex/2c9308e48782549881e8bcbbe7865af68/lantiq},
groups = {public},
interhash = {b31bb5f06848e705c54ee97dec30bbdc},
intrahash = {c9308e48782549881e8bcbbe7865af68},
keywords = {networks graphs},
publisher = {Addison-Wesley},
timestamp = {2011-12-08T16:36:57.000+0100},
title = {Graph Theory},
username = {lantiq},
year = 1969
}

@article{Karp,
author = {Karp, R. M.},
title = {On the Computational Complexity of Combinatorial Problems},
journal = {Networks},
volume = {5},
number = {1},
pages = {45-68},
doi = {https://doi.org/10.1002/net.1975.5.1.45},
url = {https://onlinelibrary.wiley.com/doi/abs/10.1002/net.1975.5.1.45},
eprint = {https://onlinelibrary.wiley.com/doi/pdf/10.1002/net.1975.5.1.45},
abstract = {A large class of classical combinatorial problems, including most of the difficult problems in the literature of network flows and computational graph theory, are shown to be equivalent, in the sense that either all or none of them can be solved in polynomial time. Moreover, they are solvable in polynomial time if and only if every problem solvable by a polynomial-depth backtrack search is also solvable by a polynomial-time algorithm. The technique of deriving these results through problem transformations is explained, and some comments are made as to the probable effect of these results on research in the field of combinatorial algorithms.},
year = {1975}
}

@book{Borodin,
title={Online Computation and Competitive Analysis},
author={Borodin, A. and El-Yaniv, R.},
isbn={9780521619462},
lccn={97038652},
url={https://books.google.ca/books?id=v3faI8pER6IC},
year={2005},
publisher={Cambridge University Press}
}

@article{DW,
author = {Dreyfus, S. E. and Wagner, R. A.},
title = {The steiner problem in graphs},
journal = {Networks},
volume = {1},
number = {3},
pages = {195-207},
doi = {https://doi.org/10.1002/net.3230010302},
url = {https://onlinelibrary.wiley.com/doi/abs/10.1002/net.3230010302},
eprint = {https://onlinelibrary.wiley.com/doi/pdf/10.1002/net.3230010302},
abstract = {Abstract An algorithm for solving the Steiner problem on a finite undirected graph is presented. This algorithm computes the set of graph arcs of minimum total length needed to connect a specified set of k graph nodes. If the entire graph contains n nodes, the algorithm requires time proportional to n3/2 + n2 (2k-1 - k - 1) + n(3k-1 - 2k + 3)/2. The time requirement above includes the term n3/2, which can be eliminated if the set of shortest paths connecting each pair of nodes in the graph is available.},
year = {1971}
}

@misc{Bjorketal,
title={Fourier meets M\"{o}bius: fast subset convolution},
author={Andreas Björklund and Thore Husfeldt and Petteri Kaski and Mikko Koivisto},
year={2006},
eprint={cs/0611101},
archivePrefix={arXiv},
primaryClass={cs.DS},
url={https://arxiv.org/abs/cs/0611101},
}


@article{Nederlof,
title = "Fast polynomial-space algorithms using inclusion-exclusion",
abstract = "Given a graph with n vertices, k terminals and positive integer weights not larger than c, we compute a minimum Steiner Tree in O¿(2kc) time and O¿(c) space, where the O¿ notation omits terms bounded by a polynomial in the input-size. We obtain the result by defining a generalization of walks, called branching walks, and combining it with the Inclusion-Exclusion technique. Using this combination we also give O¿(2n)-time polynomial space algorithms for Degree Constrained Spanning Tree, Maximum Internal Spanning Tree and #Spanning Forest with a given number of components. Furthermore, using related techniques, we also present new polynomial space algorithms for computing the Cover Polynomial of a graph, Convex Tree Coloring and counting the number of perfect matchings of a graph. Keywords: Inclusion-Exclusion; Fixed parameter tractability; Exact algorithms; Polynomial space; Steiner tree",
author = "J. Nederlof",
year = "2013",
doi = "10.1007/s00453-012-9630-x",
language = "English",
volume = "65",
pages = "868--884",
journal = "Algorithmica",
issn = "0178-4617",
publisher = "Springer",
number = "4",
}

@article{Vygen,
title = {Faster algorithm for optimum Steiner trees},
journal = {Information Processing Letters},
volume = {111},
number = {21},
pages = {1075-1079},
year = {2011},
issn = {0020-0190},
doi = {https://doi.org/10.1016/j.ipl.2011.08.005},
url = {https://www.sciencedirect.com/science/article/pii/S0020019011002341},
author = {Jens Vygen},
keywords = {Graph algorithms, Design of algorithms, Steiner tree problem, Dynamic programming, Tree composition},
abstract = {We present a new deterministic algorithm for the Steiner tree problem in weighted graphs. Its running time is O(nk2k+(log2k)(log2n)), where n is the number of vertices and k is the number of terminals. This is faster than all previously known algorithms if logn(loglogn)3<k<(n−log2n)/2. Our algorithm is based on a new tree composition theorem.}
}

@article{RZ,
title={Tighter Bounds for Graph Steiner Tree Approximation},
author={Gabriel Robins and Alex Zelikovsky},
journal={SIAM J. Discret. Math.},
year={2005},
volume={19},
pages={122-134},
url={https://api.semanticscholar.org/CorpusID:17353352}
}

@article{Byrketal,
author = {Byrka, Jaros\l{}aw and Grandoni, Fabrizio and Rothvoss, Thomas and Sanit\`{a}, Laura},
title = {Steiner Tree Approximation via Iterative Randomized Rounding},
year = {2013},
issue_date = {February 2013},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {60},
number = {1},
issn = {0004-5411},
url = {https://doi.org/10.1145/2432622.2432628},
doi = {10.1145/2432622.2432628},
abstract = {The Steiner tree problem is one of the most fundamental NP-hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for this problem was improved from 2 to 1.55 [Robins and Zelikovsky 2005]. All these algorithms are purely combinatorial. A long-standing open problem is whether there is an LP relaxation of Steiner tree with integrality gap smaller than 2 [Rajagopalan and Vazirani 1999].In this article we present an LP-based approximation algorithm for Steiner tree with an improved approximation factor. Our algorithm is based on a, seemingly novel, iterative randomized rounding technique. We consider an LP relaxation of the problem, which is based on the notion of directed components. We sample one component with probability proportional to the value of the associated variable in a fractional solution: the sampled component is contracted and the LP is updated consequently. We iterate this process until all terminals are connected. Our algorithm delivers a solution of cost at most ln(4) + ε < 1.39 times the cost of an optimal Steiner tree. The algorithm can be derandomized using the method of limited independence.As a by-product of our analysis, we show that the integrality gap of our LP is at most 1.55, hence answering the mentioned open question.},
journal = {J. ACM},
month = feb,
articleno = {6},
numpages = {33},
keywords = {Approximation algorithms, linear programming relaxations, network design, randomized algorithms}
}

@inproceedings{Goemetal,
author = {Goemans, Michel X. and Olver, Neil and Rothvo\ss{}, Thomas and Zenklusen, Rico},
title = {Matroids and integrality gaps for hypergraphic steiner tree relaxations},
year = {2012},
isbn = {9781450312455},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2213977.2214081},
doi = {10.1145/2213977.2214081},
abstract = {Until recently, LP relaxations have only played a very limited role in the design of approximation algorithms for the Steiner tree problem. In particular, no (efficiently solvable) Steiner tree relaxation was known to have an integrality gap bounded away from 2, before Byrka et al. [3] showed an upper bound of ~1.55 of a hypergraphic LP relaxation and presented a ln(4)+ε ~1.39 approximation based on this relaxation. Interestingly, even though their approach is LP based, they do not compare the solution produced against the LP value. We take a fresh look at hypergraphic LP relaxations for the Steiner tree problem---one that heavily exploits methods and results from the theory of matroids and submodular functions---which leads to stronger integrality gaps, faster algorithms, and a variety of structural insights of independent interest. More precisely, along the lines of the algorithm of Byrka et al.[3], we present a deterministic ln(4)+ε approximation that compares against the LP value and therefore proves a matching ln(4) upper bound on the integrality gap of hypergraphic relaxations.Similarly to [3], we iteratively fix one component and update the LP solution. However, whereas in [3] the LP is solved at every iteration after contracting a component, we show how feasibility can be maintained by a greedy procedure on a well-chosen matroid. Apart from avoiding the expensive step of solving a hypergraphic LP at each iteration, our algorithm can be analyzed using a simple potential function. This potential function gives an easy means to determine stronger approximation guarantees and integrality gaps when considering restricted graph topologies. In particular, this readily leads to a 73/60 ~1.217 upper bound on the integrality gap of hypergraphic relaxations for quasi-bipartite graphs.Additionally, for the case of quasi-bipartite graphs, we present a simple algorithm to transform an optimal solution to the bidirected cut relaxation to an optimal solution of the hypergraphic relaxation, leading to a fast 73/60 approximation for quasi-bipartite graphs. Furthermore, we show how the separation problem of the hypergraphic relaxation can be solved by computing maximum flows, which provides a way to obtain a fast independence oracle for the matroids that we use in our approach.},
booktitle = {Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing},
pages = {1161–1176},
numpages = {16},
keywords = {approximation algorithms, integrality gaps, linear programming relaxations, matroids},
location = {New York, New York, USA},
series = {STOC '12}
}

@article{Luczak,
title = {Size and connectivity of the k-core of a random graph},
journal = {Discrete Mathematics},
volume = {91},
number = {1},
pages = {61-68},
year = {1991},
issn = {0012-365X},
doi = {https://doi.org/10.1016/0012-365X(91)90162-U},
url = {https://www.sciencedirect.com/science/article/pii/0012365X9190162U},
author = {Tomasz Łuczak},
abstract = {Let G(n, p) be a graph with n labelled vertices in which each edge is present independently with probability p = p(n) and let C(k; n, p) be the maximal subgraph of G(n, p) with the minimal degree at least k = k(n). In this paper we estimate the size of C(k; n, p) and consider the probability that C(k; n, p) is k-connected when n→∞.}
}

@book{rosenHandbook,
title={Handbook of Discrete and Combinatorial Mathematics},
author={Rosen, K.H.},
isbn={9781439832905},
lccn={99048378},
series={Discrete Mathematics and Its Applications},
url={https://books.google.ca/books?id=yJIMx9nXB6kC},
year={1999},
publisher={Taylor \& Francis}
}

@Inbook{OAST,
author="Zachariasen, Martin
and Winter, Pawel",
title="Obstacle-Avoiding Euclidean Steiner Trees in the Plane: An Exact Algorithm",
bookTitle="Algorithm Engineering and Experimentation: International Workshop ALENEX'99 Baltimore, MD, USA, January 15--16, 1999 Selected Papers",
year="1999",
publisher="Springer Berlin Heidelberg",
address="Berlin, Heidelberg",
pages="286--299",
abstract="The first exact algorithm for the obstacle-avoiding Euclidean Steiner tree problem in the plane (in its most general form) is presented. The algorithm uses a two-phase framework --- based on the generation and concatenation of full Steiner trees --- previously shown to be very successful for the obstacle-free case. Computational results for moderate size problem instances are given; instances with up to 150 terminals have been solved to optimality within a few hours of CPU-time.",
isbn="978-3-540-48518-6",
doi="10.1007/3-540-48518-X_17",
url="https://doi.org/10.1007/3-540-48518-X_17"
}

@article{Gaoetal,
title = {Hypergraph Computation},
journal = {Engineering},
volume = {40},
pages = {188-201},
year = {2024},
issn = {2095-8099},
doi = {https://doi.org/10.1016/j.eng.2024.04.017},
url = {https://www.sciencedirect.com/science/article/pii/S2095809924002510},
author = {Yue Gao and Shuyi Ji and Xiangmin Han and Qionghai Dai},
keywords = {High-order correlation, Hypergraph structure modeling, Hypergraph semantic computing, Efficient hypergraph computing, Hypergraph computation framework},
abstract = {Practical real-world scenarios such as the Internet, social networks, and biological networks present the challenges of data scarcity and complex correlations, which limit the applications of artificial intelligence. The graph structure is a typical tool used to formulate such correlations, it is incapable of modeling high-order correlations among different objects in systems; thus, the graph structure cannot fully convey the intricate correlations among objects. Confronted with the aforementioned two challenges, hypergraph computation models high-order correlations among data, knowledge, and rules through hyperedges and leverages these high-order correlations to enhance the data. Additionally, hypergraph computation achieves collaborative computation using data and high-order correlations, thereby offering greater modeling flexibility. In particular, we introduce three types of hypergraph computation methods: ① hypergraph structure modeling, ② hypergraph semantic computing, and ③ efficient hypergraph computing. We then specify how to adopt hypergraph computation in practice by focusing on specific tasks such as three-dimensional (3D) object recognition, revealing that hypergraph computation can reduce the data requirement by 80% while achieving comparable performance or improve the performance by 52% given the same data, compared with a traditional data-based method. A comprehensive overview of the applications of hypergraph computation in diverse domains, such as intelligent medicine and computer vision, is also provided. Finally, we introduce an open-source deep learning library, DeepHypergraph (DHG), which can serve as a tool for the practical usage of hypergraph computation.}
}

@article{Molnar,
author = {Molnár, Bálint},
year = {2014},
month = {09},
pages = {261-282},
title = {APPLICATIONS OF HYPERGRAPHS IN INFORMATICS: A SURVEY AND OPPORTUNITIES FOR RESEARCH},
volume = {42},
journal = {ANNALES UNIVERSITATIS SCIENTIARUM BUDAPESTINENSIS DE ROLANDO EOTVOS NOMINATAE SECTIO COMPUTATORICA (ISSN: 0138-9491)}
}

@article{Galloetal,
title = {Directed hypergraphs and applications},
journal = {Discrete Applied Mathematics},
volume = {42},
number = {2},
pages = {177-201},
year = {1993},
issn = {0166-218X},
doi = {https://doi.org/10.1016/0166-218X(93)90045-P},
url = {https://www.sciencedirect.com/science/article/pii/0166218X9390045P},
author = {Giorgio Gallo and Giustino Longo and Stefano Pallottino and Sang Nguyen},
abstract = {We deal with directed hypergraphs as a tool to model and solve some classes of problems arising in operations research and in computer science. Concepts such as connectivity, paths and cuts are defined. An extension of the main duality results to a special class of hypergraphs is presented. Algorithms to perform visits of hypergraphs and to find optimal paths are studied in detail. Some applications arising in propositional logic, And-Or graphs, relational databases and transportation analysis are presented.}
}

@article{Hakimi,
author = {Hakimi, S. L.},
title = {Steiner's problem in graphs and its implications},
journal = {Networks},
volume = {1},
number = {2},
pages = {113-133},
doi = {https://doi.org/10.1002/net.3230010203},
url = {https://onlinelibrary.wiley.com/doi/abs/10.1002/net.3230010203},
eprint = {https://onlinelibrary.wiley.com/doi/pdf/10.1002/net.3230010203},
abstract = {Abstract A graph theoretic version of Steiner's problem in plane geometry is described. An approach for solving this problem, related to Melzak's solution to Steiner's problem, is presented. The problems of finding “shortest route” and “minimal spanning tree” in graphs become special cases of the Steiner's problem in graphs. It is shown that a solution to this problem also provides us with a solution to the problems of finding a minimum externally stable set and a maximum internally stable set in a graph.},
year = {1971}
}

@inproceedings{Levin,
title={Algorithm for the shortest connection of a group of graph vertices},
author={Levin, A Yu},
booktitle={Dokl. Akad. Nauk SSSR},
volume={200},
pages={773--776},
year={1971}
}

@incollection{Maculan,
title = {The Steiner Problem in Graphs**This work was partially supported by Conselho Nacional de Desenvolvimento Cientifico e Tecnologico, CNPq 300195-83 and by FINEP.},
editor = {Silvano Martello and Gilbert Laporte and Michel Minoux and Celso Ribeiro},
series = {North-Holland Mathematics Studies},
publisher = {North-Holland},
volume = {132},
pages = {185-211},
year = {1987},
booktitle = {Surveys in Combinatorial Optimization},
issn = {0304-0208},
doi = {https://doi.org/10.1016/S0304-0208(08)73236-5},
url = {https://www.sciencedirect.com/science/article/pii/S0304020808732365},
author = {Nelson Maculan},
abstract = {Publisher Summary
This chapter reviews formulations and some procedures that have been suggested for the solution of the Steiner Problem in graphs. It presents the definition and results associated with the classical Steiner Problem also known as the Euclidean Steiner Problem (ESP). The chapter discusses the Steiner Problem in graphs where the Steiner Problem in an undirected graph (SPUG) and the Steiner Problem in a directed graph (SPDG) are defined. It also discusses the transformation of a SPUG in a SPDG. The chapter provides an overview on the Lawler algorithm for the SPUG. The chaptre presents four integer programming formulations of the Steiner Problem in graphs, compares the linear relaxations of three of these formulations, and describes an application of Benders method to solve one of these formulations illustrated by an example. It also presents solution methods based on these formulations and describes some computational results.}
}

@article{Winter,
author = {Winter, Pawel},
title = {Steiner problem in networks: A survey},
journal = {Networks},
volume = {17},
number = {2},
pages = {129-167},
doi = {https://doi.org/10.1002/net.3230170203},
url = {https://onlinelibrary.wiley.com/doi/abs/10.1002/net.3230170203},
eprint = {https://onlinelibrary.wiley.com/doi/pdf/10.1002/net.3230170203},
abstract = {Abstract The problem of determining a minimum cost connected network (i.e., weighted graph) G that spans a given subset of vertices is known in the literature as the Steiner problem in networks. We survey exact algorithms and heuristics which appeared in the published literature. We also discuss problems related to the Steiner problem in networks.},
year = {1987}
}

@inproceedings{Voss,
author="Duin, Cees
and Vo{\ss}, Stefan",
title="Steiner Tree Heuristics --- A Survey",
booktitle="Operations Research Proceedings 1993",
year="1994",
publisher="Springer Berlin Heidelberg",
address="Berlin, Heidelberg",
pages="485--496",
abstract="Given a graph with weights on its edges Steiner's problem in graphs is to determine a minimum cost subgraph spanning a set of specified vertices. Real world problems arising in the layout of connection structures in networks as, e.g., in topological network design or VLSI design may often be decomposed into a number of well known combinatorial optimization problems. Steiner's problem in graphs is included within this context. According to its complexity one is interested in developing efficient heuristic algorithms to find good approximate solutions. In this paper we give a survey on recent results on heuristic methods for the problem.",
isbn="978-3-642-78910-6"
}

@inbook{Azarpred,
author = {Yossi Azar and Debmalya Panigrahi and Noam Touitou},
title = {Online Graph Algorithms with Predictions},
booktitle = {Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
publisher = {Society for Industrial and Applied Mathematics},
year = {2022},
chapter = {},
pages = {35-66},
doi = {10.1137/1.9781611977073.3},
URL = {https://epubs.siam.org/doi/abs/10.1137/1.9781611977073.3},
eprint = {https://epubs.siam.org/doi/pdf/10.1137/1.9781611977073.3},
abstract = { Online algorithms with predictions is a popular and elegant framework for bypassing pessimistic lower bounds in competitive analysis. In this model, online algorithms are supplied with future predictions and the goal is for the competitive ratio to smoothly interpolate between the best offline and online bounds as a function of the prediction error. In this paper, we study online graph problems with predictions. Our contributions are the following: The first question is defining prediction error. For graph/metric problems, there can be two types of error, locations that are not predicted, and locations that are predicted but the predicted and actual locations do not coincide exactly. We design a novel definition of prediction error called metric error with outliers to simultaneously capture both types of errors, which thereby generalizes previous definitions of error that only capture one of the two error types. We give a general framework for obtaining online algorithms with predictions that combines, in a “black box” fashion, existing online and offline algorithms, under certain technical conditions. To the best of our knowledge, this is the first general-purpose tool for obtaining online algorithms with predictions. Using our framework, we obtain tight bounds on the competitive ratio of several classical graph problems as a function of metric error with outliers: Steiner tree, Steiner forest, priority Steiner tree/forest, and uncapacitated/capacitated facility location. Both the definition of metric error with outliers and the general framework for combining offline and online algorithms are not specific to the problems that we consider in this paper. We hope that these will be useful for future work on other problems in this domain. }
}

@article{Xupred,
title={Learning-Augmented Algorithms for Online Steiner Tree},
volume={36},
url={https://ojs.aaai.org/index.php/AAAI/article/view/20854},
DOI={10.1609/aaai.v36i8.20854},
abstractNote={This paper considers the recently popular beyond-worst-case algorithm analysis model which integrates machine-learned predictions with online algorithm design. We consider the online Steiner tree problem in this model for both directed and undirected graphs. Steiner tree is known to have strong lower bounds in the online setting and any algorithm’s worst-case guarantee is far from desirable. This paper considers algorithms that predict which terminal arrives online. The predictions may be incorrect and the algorithms’ performance is parameterized by the number of incorrectly predicted terminals. These guarantees ensure that algorithms break through the online lower bounds with good predictions and the competitive ratio gracefully degrades as the prediction error grows. We then observe that the theory is predictive of what will occur empirically. We show on graphs where terminals are drawn from a distribution, the new online algorithms have strong performance even with modestly correct predictions.},
number={8},
journal={Proceedings of the AAAI Conference on Artificial Intelligence},
author={Xu, Chenyang and Moseley, Benjamin},
year={2022},
month={Jun.},
pages={8744-8752} }

@misc{Panilec,
author = {Debmalya Panigrahi},
title = {{COMPSCI 638: Graph Algorithms, Lecture 16}},
howpublished = "\url{https://courses.cs.duke.edu/fall19/compsci638/fall19_notes/lecture16.pdf}",
year = {2019},
note = "[Online; accessed 22-02-2024]"
}

@Inbook{Pedersen,
author="Pedersen, Jaap
and Ljubi{\'{c}}, Ivana",
editor="Pardalos, Panos M.
and Prokopyev, Oleg A.",
title="Prize-Collecting Steiner Tree Problem and Its Variants",
bookTitle="Encyclopedia of Optimization",
year="2025",
publisher="Springer International Publishing",
address="Cham",
pages="1--11",
isbn="978-3-030-54621-2",
doi="10.1007/978-3-030-54621-2_869-1",
url="https://doi.org/10.1007/978-3-030-54621-2_869-1"
}

@inproceedings{Johnson,
author = {Johnson, David S. and Minkoff, Maria and Phillips, Steven},
title = {The prize collecting Steiner tree problem: theory and practice},
year = {2000},
isbn = {0898714532},
publisher = {Society for Industrial and Applied Mathematics},
address = {USA},
booktitle = {Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms},
pages = {760–769},
numpages = {10},
location = {San Francisco, California, USA},
series = {SODA '00}
}

@inproceedings{Dehghani,
author = {Dehghani, Sina and Ehsani, Soheil and Hajiaghayi, MohammadTaghi and Liaghat, Vahid},
title = {Online degree-bounded steiner network design},
year = {2016},
isbn = {9781611974331},
publisher = {Society for Industrial and Applied Mathematics},
address = {USA},
abstract = {We initiate the study of degree-bounded network design problems in the online setting. The degree-bounded Steiner tree problem -- which asks for a subgraph with minimum degree that connects a given set of vertices -- is perhaps one of the most representative problems in this class. This paper deals with its well-studied generalization called the degree-bounded Steiner forest problem where the connectivity demands are represented by vertex pairs that need to be individually connected. In the classical online model, the input graph is given offline but the demand pairs arrive sequentially in online steps. The selected subgraph starts off as the empty subgraph, but has to be augmented to satisfy the new connectivity constraint in each online step. The goal is to be competitive against an adversary that knows the input in advance.The standard techniques for solving degree-bounded problems often fall in the category of iterative and dependent rounding techniques. Unfortunately, these rounding methods are inherently difficult to adapt to an online settings since the underlying fractional solution may change dramatically in between the rounding steps. Indeed, this might be the very reason that despite many advances in the online network design paradigm in the past two decades, the natural family of degree-bounded problems has remained widely open.In this paper, we design an intuitive greedy-like algorithm that achieves a competitive ratio of O(log n) where n is the number of vertices. We show that no (randomized) algorithm can achieve a (multiplicative) competitive ratio o(log n); thus our result is asymptotically tight. We further show strong hardness results for the group Steiner tree and the edge-weighted variants of degree-bounded connectivity problems.F\"{u}rer and Raghavachari resolved the offline variant of degree-bounded Steiner forest in their paper in SODA'92. Since then, the family of degree-bounded network design problems has been extensively studied in the literature resulting in the development of many interesting tools and numerous papers on the topic. We hope that our approach and its dual analysis, paves the way for solving the online variants of the classical problems in this family of problems.},
booktitle = {Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms},
pages = {164–175},
numpages = {12},
location = {Arlington, Virginia},
series = {SODA '16}
}

@inproceedings{Gupta,
author = {Gupta, Anupam and Kumar, Amit},
title = {Online steiner tree with deletions},
year = {2014},
isbn = {9781611973389},
publisher = {Society for Industrial and Applied Mathematics},
address = {USA},
abstract = {In the online Steiner tree problem, the input is a set of vertices that appear one-by-one, and we have to maintain a Steiner tree on the current set of vertices. The cost of the tree is the total length of edges in the tree, and we want this cost to be close to the cost of the optimal Steiner tree at all points in time. If we are allowed to only add edges, a tight bound of Θ(log n) on the competitiveness has been known for two decades. Recently it was shown that if we can add one new edge and make one edge swap upon every vertex arrival, we can still maintain a constant-competitive tree online.But what if the set of vertices sees both additions and deletions? Again, we would like to obtain a low-cost Steiner tree with as few edge changes as possible. The original paper of Imase and Waxman (SIAM J. Disc. Math, 4(3): 369--384, 1991) had also considered this model, and it gave an algorithm that made at most O(n3/2) edge changes for the first n requests, and maintained a constant-competitive tree online. In this paper we improve on these results:• We give an online algorithm that maintains a Steiner tree under only deletions: we start off with a set of vertices, and at each time one of the vertices is removed from this set---our Steiner tree no longer has to span this vertex. We give an algorithm that changes only a constant number of edges upon each request, and maintains a constant-competitive tree at all times. Our algorithm uses the primal-dual framework and a global charging argument to carefully make these constant number of changes.• We also give an algorithm that maintains a Steiner tree in the fully-dynamic model (where each request either adds or deletes a vertex). Our algorithm for this setting makes a constant number of changes per request in an amortized sense.},
booktitle = {Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms},
pages = {455–467},
numpages = {13},
location = {Portland, Oregon},
series = {SODA '14}
}



@InProceedings{Dehgani2,
author = {Dehghani, Sina and Ehsani, Soheil and Hajiaghayi, Mohammad Taghi and Liaghat, Vahid and R\"{a}cke, Harald and Seddighin, Saeed},
title = {{Online Weighted Degree-Bounded Steiner Networks via Novel Online Mixed Packing/Covering}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {42:1--42:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-013-2},
ISSN = {1868-8969},
year = {2016},
volume = {55},
editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.42},
URN = {urn:nbn:de:0030-drops-63221},
doi = {10.4230/LIPIcs.ICALP.2016.42},
annote = {Keywords: Online, Steiner Tree, Approximation, Competitive ratio}
}

@article{Angelopoulos,
author = {Angelopoulos, Spyros},
title = {Parameterized Analysis of the Online Priority and Node-Weighted Steiner Tree Problems},
year = {2019},
issue_date = {August 2019},
publisher = {Springer-Verlag},
address = {Berlin, Heidelberg},
volume = {63},
number = {6},
issn = {1432-4350},
url = {https://doi.org/10.1007/s00224-019-09922-2},
doi = {10.1007/s00224-019-09922-2},
abstract = {In this paper we study the online variant of two well-known Steiner tree problems. In the online setting, the input consists of a sequence of terminals; upon arrival of a terminal, the online algorithm must irrevocably buy a subset of edges and vertices of the graph so as to guarantee the connectivity of the currently revealed part of the input. More precisely, we first study the online node-weighted Steiner tree problem, in which both edges and vertices are weighted, and the objective is to minimize the total cost of edges and vertices in the solution. We then address the online priority Steiner tree problem, in which each edge and each request are associated with a priority value, which corresponds to their bandwidth support and requirement, respectively. Both problems have applications in the domain of multicast network communications and have been studied from the point of view of approximation algorithms. Motivated by the observation that competitive analysis gives very pessimistic and unsatisfactory results when the only relevant parameter is the number of terminals, we introduce an approach based on parameterized analysis of online algorithms. In particular, we base the analysis on additional parameters that help reveal the true complexity of the underlying problem, and allow a much finer classification of online algorithms based on their performance. More specifically, for the online node-weighted Steiner tree problem, we show a tight bound of ?(max{min{?,k},log k}) on the competitive ratio, where ? is the ratio of the maximum node weight to the minimum node weight and k is the number of terminals. For the online priority Steiner tree problem, we show corresponding tight bounds of ?(blogkb)${Theta }(blog frac {k}{b})$, when k >b and ?(k), when k ≤ b, where b is the number of priority levels and k is the number of terminals. Our main results apply to both deterministic and randomized algorithms, as well as to generalized versions of the problems (i.e., to Steiner forest variants).},
journal = {Theor. Comp. Sys.},
month = aug,
pages = {1413–1447},
numpages = {35},
keywords = {Steiner tree problems, Online algorithms, Multicasting, Models of communication networks, Competitive analysis}
}

@InProceedings{Demaine,
author="Demaine, Erik D.
and Hajiaghayi, MohammadTaghi
and Klein, Philip N.",
editor="Albers, Susanne
and Marchetti-Spaccamela, Alberto
and Matias, Yossi
and Nikoletseas, Sotiris
and Thomas, Wolfgang",
title="Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs",
booktitle="Automata, Languages and Programming",
year="2009",
publisher="Springer Berlin Heidelberg",
address="Berlin, Heidelberg",
pages="328--340",
abstract="We improve the approximation ratios for two optimization problems in planar graphs. For node-weighted Steiner tree, a classical network-optimization problem, the best achievable approximation ratio in general graphs is $\Theta$(logn), and nothing better was previously known for planar graphs. We give a constant-factor approximation for planar graphs. Our algorithm generalizes to allow as input any nontrivial minor-closed graph family, and also generalizes to address other optimization problems such as Steiner forest, prize-collecting Steiner tree, and network-formation games.",
isbn="978-3-642-02927-1"
}

@article{Segev,
title={The node-weighted Steiner tree problem},
author={Segev, Arie},
journal={Networks},
volume={17},
number={1},
pages={1--17},
year={1987},
publisher={Wiley Online Library}
}

@article{Klein,
title = {A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees},
journal = {Journal of Algorithms},
volume = {19},
number = {1},
pages = {104-115},
year = {1995},
issn = {0196-6774},
doi = {https://doi.org/10.1006/jagm.1995.1029},
url = {https://www.sciencedirect.com/science/article/pii/S0196677485710292},
author = {P. Klein and R. Ravi},
abstract = {We give the first approximation algorithm for the node-weighted Steiner tree problem. Its performance guarantee is within a constant factor of the best possible unless P̃ ⊇ NP. (P̃ stands for the complexity class deterministic quasi-polynomial time, or DTIME[npolylog n].) Our algorithm generalizes to handle other network-design problems.}
}

@article{Moss,
author = {Moss, A. and Rabani, Y.},
title = {Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems},
journal = {SIAM Journal on Computing},
volume = {37},
number = {2},
pages = {460-481},
year = {2007},
doi = {10.1137/S0097539702420474},
URL = { https://doi.org/10.1137/S0097539702420474},
eprint = {https://doi.org/10.1137/S0097539702420474},
abstract = { We consider a class of optimization problems where the input is an undirected graph with two weight functions defined for each node, namely the node's profit and its cost. The goal is to find a connected set of nodes of low cost and high profit. We present approximation algorithms for three natural optimization criteria that arise in this context, all of which are NP-hard. The budget problem asks for maximizing the profit of the set subject to a budget constraint on its cost. The quota problem requires minimizing the cost of the set subject to a quota constraint on its profit. Finally, the prize collecting problem calls for minimizing the cost of the set plus the profit (here interpreted as a penalty) of the complement set. For all three problems, our algorithms give an approximation guarantee of \$O(\log n)\$, where n is the number of nodes. To the best of our knowledge, these are the first approximation results for the quota problem and for the prize collecting problem, both of which are at least as hard to approximate as the set cover. For the budget problem, our results improve on a previous \$O(\log^2 n)\$ result of Guha et al. Our methods involve new theorems relating tree packings to (node) cut conditions. We also show similar theorems (with better bounds) using edge cut conditions. These imply bounds for the analogous budget and quota problems with edge costs which are comparable to known (constant factor) bounds. }
}

@article{Garg2,
title = {A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem},
journal = {Journal of Algorithms},
volume = {37},
number = {1},
pages = {66-84},
year = {2000},
issn = {0196-6774},
doi = {https://doi.org/10.1006/jagm.2000.1096},
url = {https://www.sciencedirect.com/science/article/pii/S0196677400910964},
author = {Naveen Garg and Goran Konjevod and R. Ravi},
keywords = {Steiner tree, approximation algorithms, set cover, randomized rounding, network design, tree decompositions},
abstract = {Given a weighted graph with some subsets of vertices called groups, the group Steiner tree problem is to find a minimum-weight subgraph which contains at least one vertex from each group. We give a randomized algorithm with a polylogarithmic approximation guarantee for the group Steiner tree problem. The previous best approximation guarantee was O(i2k1/i) in time O(nik2i) (Charikar, Chekuri, Goel, and Guha). Our algorithm also improves existing approximation results for network design problems with location-based constraints and for the symmetric generalized traveling salesman problem.}
}

@InProceedings{Sahneh,
author="Sahneh, Faryad Darabi
and Kobourov, Stephen
and Spence, Richard",
editor="Chen, Chi-Yeh
and Hon, Wing-Kai
and Hung, Ling-Ju
and Lee, Chia-Wei",
title="Approximation Algorithms for Priority Steiner Tree Problems",
booktitle="Computing and Combinatorics",
year="2021",
publisher="Springer International Publishing",
address="Cham",
pages="112--123",
abstract="In the Priority Steiner Tree (PST) problem, we are given an undirected graph {\$}{\$}G=(V,E){\$}{\$}G=(V,E)with a source {\$}{\$}s {\backslash}in V{\$}{\$}s∈Vand terminals {\$}{\$}T {\backslash}subseteq V {\backslash}setminus {\backslash}{\{}s{\backslash}{\}}{\$}{\$}T⊆V{\backslash}{\{}s{\}}, where each terminal {\$}{\$}v {\backslash}in T{\$}{\$}v∈Trequires a nonnegative priority P(v). The goal is to compute a minimum weight Steiner tree containing edges of varying rates such that the path from s to each terminal v consists of edges of rate greater than or equal to P(v). The PST problem with k priorities admits a {\$}{\$}{\backslash}min {\backslash}{\{}2 {\backslash}ln |T| + 2, k{\backslash}rho {\backslash}{\}}{\$}{\$}min{\{}2ln|T|+2,k$\rho${\}}-approximation [Charikar et al., 2004], and is hard to approximate with ratio {\$}{\$}c {\backslash}log {\backslash}log n{\$}{\$}cloglognfor some constant c [Chuzhoy et al., 2008]. In this paper, we first strengthen the analysis provided by [Charikar et al., 2004] for the {\$}{\$}(2 {\backslash}ln |T| + 2){\$}{\$}(2ln|T|+2)-approximation to show an approximation ratio of {\$}{\$}{\backslash}lceil {\backslash}log {\_}2 |T| {\backslash}rceil + 1 {\backslash}le 1.443 {\backslash}ln |T| + 2{\$}{\$}⌈log2|T|⌉+1≤1.443ln|T|+2, then provide a very simple, parallelizable algorithm which achieves the same approximation ratio. We then consider a more difficult node-weighted version of the PST problem, and provide a {\$}{\$}(2 {\backslash}ln |T|+2){\$}{\$}(2ln|T|+2)-approximation using extensions of the spider decomposition by [Klein {\&} Ravi, 1995]. This is the first result for the PST problem in node-weighted graphs. Moreover, the approximation ratios for all above algorithms are tight.",
isbn="978-3-030-89543-3"
}

@techreport{Cornuejols,
title={The uncapicitated facility location problem},
author={Cornu{\'e}jols, G{\'e}rard and Nemhauser, George and Wolsey, Laurence},
year={1983},
institution={Cornell University Operations Research and Industrial Engineering}
}

@inproceedings{shmoys,
title={Approximation algorithms for facility location problems},
author={Shmoys, David B and Tardos, {\'E}va and Aardal, Karen},
booktitle={Proceedings of the twenty-ninth annual ACM symposium on Theory of computing},
pages={265--274},
year={1997}
}

@article{kerivin,
title={Design of survivable networks: A survey},
author={Kerivin, Herv{\'e} and Mahjoub, A Ridha},
journal={Networks: An International Journal},
volume={46},
number={1},
pages={1--21},
year={2005},
publisher={Wiley Online Library}
}

@inproceedings{hajiaghayi,
title={Near-optimal online algorithms for prize-collecting steiner problems},
author={Hajiaghayi, MohammadTaghi and Liaghat, Vahid and Panigrahi, Debmalya},
booktitle={Automata, Languages, and Programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I 41},
pages={576--587},
year={2014},
organization={Springer}
}

@inproceedings{alon,
title={The online set cover problem},
author={Alon, Noga and Awerbuch, Baruch and Azar, Yossi},
booktitle={Proceedings of the thirty-fifth annual ACM symposium on Theory of computing},
pages={100--105},
year={2003}
}

@article{caprara,
title={Algorithms for the set covering problem},
author={Caprara, Alberto and Toth, Paolo and Fischetti, Matteo},
journal={Annals of Operations Research},
volume={98},
number={1},
pages={353--371},
year={2000},
publisher={Springer}
}

@article{balas,
title={On the set-covering problem},
author={Balas, Egon and Padberg, Manfred W},
journal={Operations Research},
volume={20},
number={6},
pages={1152--1161},
year={1972},
publisher={INFORMS}
}

@article{korman,
title={On the use of randomization in the online set cover problem},
author={Korman, Simon},
journal={Weizmann Institute of Science},
volume={2},
pages={34},
year={2004}
}

@article{dobrev,
title={Improved analysis of the online set cover problem with advice},
author={Dobrev, Stefan and Edmonds, Jeff and Komm, Dennis and Kr{\'a}lovi{\v{c}}, Rastislav and Kr{\'a}lovi{\v{c}}, Richard and Krug, Sacha and M{\"o}mke, Tobias},
journal={Theoretical Computer Science},
volume={689},
pages={96--107},
year={2017},
publisher={Elsevier}
}

@book{warme,
title={Spanning trees in hypergraphs with applications to Steiner trees},
author={Warme, David Michael},
year={1998},
publisher={University of Virginia}
}

@article{polzin,
title={On Steiner trees and minimum spanning trees in hypergraphs},
author={Polzin, Tobias and Daneshmand, Siavash Vahdati},
journal={Operations Research Letters},
volume={31},
number={1},
pages={12--20},
year={2003},
publisher={Elsevier}
}

@inproceedings{baudis,
title={Approximating minimum spanning sets in hypergraphs and polymatroids},
author={Baudis, Gregor and Gr{\"o}pl, Clemens and Hougardy, Stefan and Nierhoff, Till and Pr{\"o}mel, Hans J{\"u}rgen},
booktitle={Proc. ICALP},
year={2000},
organization={Citeseer}
}

@article{ausiello,
title={Directed hypergraphs: introduction and fundamental algorithms—a survey},
author={Ausiello, Giorgio and Laura, Luigi},
journal={Theoretical Computer Science},
volume={658},
pages={293--306},
year={2017},
publisher={Elsevier}
}

@article{feige,
title={A threshold of ln n for approximating set cover},
author={Feige, Uriel},
journal={Journal of the ACM (JACM)},
volume={45},
number={4},
pages={634--652},
year={1998},
publisher={ACM New York, NY, USA}
}

@article{chvatal,
ISSN = {0364765X, 15265471},
URL = {http://www.jstor.org/stable/3689577},
abstract = {Let A be a binary matrix of size m × n, let $c^{T}$ be a positive row vector of length n and let e be the column vector, all of whose m components are ones. The set-covering problem is to minimize cTx subject to Ax ≥ e and x binary. We compare the value of the objective function at a feasible solution found by a simple greedy heuristic to the true optimum. It turns out that the ratio between the two grows at most logarithmically in the largest column sum of A. When all the components of $c^{T}$ are the same, our result reduces to a theorem established previously by Johnson and Lovasz.},
author = {V. Chvatal},
journal = {Mathematics of Operations Research},
number = {3},
pages = {233--235},
publisher = {INFORMS},
title = {A Greedy Heuristic for the Set-Covering Problem},
urldate = {2025-04-16},
volume = {4},
year = {1979}
}

@book{Vazirani,
author = {Vazirani, Vijay V.},
title = {Approximation algorithms},
year = {2001},
isbn = {3540653678},
publisher = {Springer-Verlag},
address = {Berlin, Heidelberg},
abstract = {This book will be of interest to the scientific community at large and, in particular, to students and researchers in Computer Science, Operation Research, and Discrete Mathematics. It can be used both as a text in a graduate course on approximation algorithms and as a supplementary text in basic undergraduate and graduate courses on algorithms.}
}

@inproceedings{johnson-setcover,
title={Approximation algorithms for combinatorial problems},
author={Johnson, David S},
booktitle={Proceedings of the fifth annual ACM symposium on Theory of computing},
pages={38--49},
year={1973}
}

@article{alon-setcover,
title={Algorithmic construction of sets for k-restrictions},
author={Noga Alon and Dana Moshkovitz and Shmuel Safra},
journal={ACM Trans. Algorithms},
year={2006},
volume={2},
pages={153-177},
url={https://api.semanticscholar.org/CorpusID:11922650}
}

@inproceedings{raz-setcover,
title={A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP},
author={Raz, Ran and Safra, Shmuel},
booktitle={Proceedings of the twenty-ninth annual ACM symposium on Theory of computing},
pages={475--484},
year={1997}
}

@inproceedings{dinur-setcover,
title={Analytical approach to parallel repetition},
author={Dinur, Irit and Steurer, David},
booktitle={Proceedings of the forty-sixth annual ACM symposium on Theory of computing},
pages={624--633},
year={2014}
}

@inproceedings{dinuretal,
author = {Dinur, Irit and Guruswami, Venkatesan and Khot, Subhash and Regev, Oded},
title = {A new multilayered PCP and the hardness of hypergraph vertex cover},
year = {2003},
isbn = {1581136749},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/780542.780629},
doi = {10.1145/780542.780629},
abstract = {Given a k-uniform hyper-graph, the Ek-Vertex-Cover problem is to find the smallest subset of vertices that intersects every hyper-edge. We present a new multilayered PCP construction that extends the Raz verifier. This enables us to prove that Ek-Vertex-Cover is NP-hard to approximate within factor (k-1-ε) for any k ≥ 3 and any ε>0. The result is essentially tight as this problem can be easily approximated within factor k. Our construction makes use of the biased Long-Code and is analyzed using combinatorial properties of s-wise t-intersecting families of subsets.},
booktitle = {Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing},
pages = {595–601},
numpages = {7},
keywords = {hardness of approximation, hypergraph vertex cover, long code, multilayered PCP},
location = {San Diego, CA, USA},
series = {STOC '03}
}

@article{khot,
title = {Vertex cover might be hard to approximate to within 2-epsilon},
journal = {Journal of Computer and System Sciences},
volume = {74},
number = {3},
pages = {335-349},
year = {2008},
note = {Computational Complexity 2003},
issn = {0022-0000},
doi = {https://doi.org/10.1016/j.jcss.2007.06.019},
url = {https://www.sciencedirect.com/science/article/pii/S0022000007000864},
author = {Subhash Khot and Oded Regev},
keywords = {Hardness of approximation, Vertex cover, Unique games conjecture},
abstract = {Based on a conjecture regarding the power of unique 2-prover-1-round games presented in [S. Khot, On the power of unique 2-Prover 1-Round games, in: Proc. 34th ACM Symp. on Theory of Computing, STOC, May 2002, pp. 767–775], we show that vertex cover is hard to approximate within any constant factor better than 2. We actually show a stronger result, namely, based on the same conjecture, vertex cover on k-uniform hypergraphs is hard to approximate within any constant factor better than k.}
}

@ARTICLE{ST-VLSI,
author={Tang, Hao and Liu, Genggeng and Chen, Xiaohua and Xiong, Naixue},
journal={IEEE Access},
title={A Survey on Steiner Tree Construction and Global Routing for VLSI Design},
year={2020},
volume={8},
number={},
pages={68593-68622},
keywords={Routing;Steiner trees;Very large scale integration;Pins;Delays;Topology;Steiner tree construction;particle swarm optimization;routing;very large scale integration;global routing},
doi={10.1109/ACCESS.2020.2986138}
}