Article
Computer Science, Information Systems
Lu Han, Changjun Wang, Dachuan Xu, Dongmei Zhang
Summary: This paper studies the prize-collecting $k$-Steiner tree problem and proposes two approximation algorithms with improved approximation ratios.
TSINGHUA SCIENCE AND TECHNOLOGY
(2022)
Article
Computer Science, Theory & Methods
Fabrizio Grandonidagger, Bundit Laekhanukitddagger, Shi Lis
Summary: In the directed Steiner tree (DST) problem, the goal is to find a minimum-cost subgraph that contains a directed path from a root to every terminal in a given directed edge-weighted graph. An approximation algorithm with an approximation ratio of O(log(2) k/ log log k) is presented, running in quasi-polynomial time. A lower bound of Omega(log(2) k/ log log k) is proven for the class of quasi-polynomial time algorithms, making the approximation ratio asymptotically optimal. The algorithm reduces DST to the group Steiner tree on trees with dependency constraint problem and approximates it using existing frameworks.
SIAM JOURNAL ON COMPUTING
(2023)
Article
Mathematics, Applied
Pavel Dvorak, Andreas E. Feldmann, Dusan Knop, Tomas Masarik, Tomas Toufar, Pavel Vesely
Summary: The study focuses on the Steiner Tree problem and its approximation and parameterization aspects, presenting an efficient parameterized approximation scheme (EPAS) and a polynomial size approximate kernelization scheme (PSAKS) for the problem. It further discusses the parameterized approximability of Directed Steiner Tree and Steiner Forest, showing the difficulty of approximation within any function of the studied parameter in Directed Steiner Tree, but the existence of an EPAS for Unweighted Directed Steiner Tree. Additionally, it proves the existence of an EPAS and a PSAKS for Steiner Forest when considering the number of connected components of an optimal solution as a parameter.
SIAM JOURNAL ON DISCRETE MATHEMATICS
(2021)
Article
Computer Science, Theory & Methods
Xingfu Li, Guihai Yu, Sandi Klavzar, Jie Hu, Bo Li
Summary: In this study, we investigated the Steiner k-eccentricity on trees, extending the concept from a previous paper. We developed a stronger properties for the Steiner k-ecc tree than what was previously known and devised a linear time algorithm to calculate the Steiner k-eccentricity of a vertex in a tree. Additionally, we established lower and upper bounds for the average Steiner k-eccentricity index of a tree using a novel technique that is easier to follow compared to the earlier one.
THEORETICAL COMPUTER SCIENCE
(2021)
Article
Computer Science, Information Systems
Takuro Fukunaga, R. Ravi, Oleksandr Rudenko, Ziye Tang
Summary: In this study, a basic class of two-layer network design problems is examined, where hubs are established at selected nodes at considerable cost to reduce the cost of operating routes between the hubs. The goal is to find a network with minimum total cost by determining the set of nodes to open hubs and the set of edges to establish. The study shows that for non-metric edge costs, there is logarithmic approximation hardness even for the special case of spanning trees, while a polynomial-time reduction is demonstrated for Steiner trees to its corresponding node-weighted version, proving a logarithmic approximation factor. When edge costs are metric, the problem is only slightly harder to approximate than its original version.
INFORMATION PROCESSING LETTERS
(2022)
Article
Computer Science, Interdisciplinary Applications
Jianping Li, Junran Lichen, Wencheng Wang, Jean Yeh, YeongNan Yeh, Xingxing Yu, Yujie Zheng
Summary: This paper discusses the 1-line minimum rectilinear Steiner tree problem and provides three main contributions: designing an algorithm to solve the 1-line-fixed-constrained minimum rectilinear Steiner tree problem, proving this algorithm is a 1.5-approximation algorithm to solve the 1-line-fixed minimum rectilinear Steiner tree problem, and presenting a 1.5-approximation algorithm to solve the 1-line minimum rectilinear Steiner tree problem through combining the algorithm for many times and a key lemma proved by techniques of computational geometry.
JOURNAL OF COMBINATORIAL OPTIMIZATION
(2022)
Article
Computer Science, Theory & Methods
Jaroslaw Byrka, Fabrizio Grandoni, Afrouz Jabal Ameli
Summary: The basic goal of survivable network design is to build a cheap network that maintains connectivity despite failures. The connectivity augmentation problem (CAP) selects a subset of extra edges to increase the edge connectivity. The best known approximation factor for this problem is 2, but this paper presents a better approximation algorithm for the cactus augmentation problem (CacAP) reducing CAP to k = 2.
SIAM JOURNAL ON COMPUTING
(2023)
Article
Management
David Whittle, Marcus Brazil, Peter Alexander Grossman, Joachim Hyam Rubinstein, Doreen A. Thomas
Summary: This paper investigates the relationship between the length of a minimum Steiner tree and a minimum spanning tree in a configuration of concyclic points in the Euclidean plane, proving a tight lower bound on their difference. This bound can be used as part of an efficient algorithm for solving the prize-collecting Euclidean Steiner tree problem.
INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH
(2022)
Article
Computer Science, Hardware & Architecture
Chen Avin, Kaushik Mondal, Stefan Schmid
Summary: This paper studies algorithmic problems related to demand-aware network design, focusing on the online adjustment of network topology to adapt to traffic patterns. The authors propose two online algorithms, one randomized and one deterministic, for designing a self-adjusting tree network for single-source, multi-destination communication. The problem is a fundamental building block for self-adjusting network designs and has connections to self-adjusting data structures.
IEEE-ACM TRANSACTIONS ON NETWORKING
(2022)
Article
Mathematics, Applied
Xingfu Li, Guihai Yu, Sandi Klavzar
Summary: This paper investigates the Steiner 3-eccentricity on trees and provides some general properties of this metric. Additionally, a tree transformation that does not increase the average Steiner 3-eccentricity is introduced, leading to the derivation of several lower and upper bounds for the average Steiner 3-eccentricity of trees.
DISCRETE APPLIED MATHEMATICS
(2021)
Article
Operations Research & Management Science
Jianping Li, Yujie Zheng, Junran Lichen, Wencheng Wang
Summary: This paper addresses the problem of minimum number of Steiner points of constrained 1-line-fixed Steiner tree and presents two algorithms to solve it: a 3-approximation algorithm for the MNSP-C1LF-ST problem and an exact algorithm for the MNSP-C1LF-MST problem using Delaunay triangulation properties and minimum spanning tree strategies with a degree constraint.
OPTIMIZATION LETTERS
(2021)
Article
Computer Science, Software Engineering
Daniel Rehfeldt, Thorsten Koch
Summary: The Steiner tree problem in graphs (SPG) has been one of the most studied problems in combinatorial optimization. While there have been advancements in approximation and complexity, the exact solution of SPG has remained largely unchallenged for almost 20 years. This article introduces new SPG techniques and integrates them into a branch-and-cut framework, achieving competitive and even superior results compared to the current state of the art.
MATHEMATICAL PROGRAMMING
(2023)
Article
Computer Science, Software Engineering
Haris Angelidakis, Dylan Hyatt-Denesik, Laura Sanita
Summary: This research provides an improved algorithm for solving the node connectivity problem, which increases the connectivity of a network from 1 to 2. The analysis of this algorithm is simpler compared to previous studies, and it also provides new insights into the iterative randomized rounding method.
MATHEMATICAL PROGRAMMING
(2023)
Article
Computer Science, Artificial Intelligence
Guangyi Zhang, Aristides Gionis
Summary: This paper investigates the trade-off between model interpretability and accuracy in decision trees and proposes an enhanced algorithm that reduces the size of decision trees while maintaining their accuracy.
DATA MINING AND KNOWLEDGE DISCOVERY
(2023)
Article
Mathematics, Applied
Marcelo P. L. Benedito, Lehilton L. C. Pedrosa, Hugo K. K. Rosado
Summary: The Cable-Trench Problem (CTP) is a generalized problem that includes the Single-Source Shortest Paths Problem (SSSP) and the Minimum Spanning Tree Problem (MST). It is proven to be NP-hard, unlike SSSP and MST which can be solved in polynomial time. A polynomial-time approximation scheme is also ruled out for CTP. The more general Steiner Cable-Trench Problem (SCTP) is also considered, and a (2.88 +is an element of)-approximation algorithm and a parameterized algorithm are presented.
DISCRETE APPLIED MATHEMATICS
(2023)
Article
Mathematics, Applied
Chia-Wei Lee, Pin-Liang Chen, Sun-Yuan Hsieh
DISCRETE APPLIED MATHEMATICS
(2015)
Article
Computer Science, Hardware & Architecture
Chia-Wei Lee, Chao-Wen Huang, Wen-Hao Pi, Sun-Yuan Hsieh
IEEE TRANSACTIONS ON COMPUTERS
(2015)
Article
Computer Science, Theory & Methods
Sun-Yuan Hsieh, Chia-Wei Lee, Chien-Hsiang Huang
INFORMATION AND COMPUTATION
(2016)
Article
Computer Science, Theory & Methods
Sun-Yuan Hsieh, Hong-Wen Huang, Chia-Wei Lee
THEORETICAL COMPUTER SCIENCE
(2016)
Article
Computer Science, Hardware & Architecture
Limei Lin, Sun-Yuan Hsieh, Riqing Chen, Li Xu, Chia-Wei Lee
IEEE TRANSACTIONS ON RELIABILITY
(2018)
Article
Computer Science, Hardware & Architecture
Li-Hsuan Chen, Dun-Wei Cheng, Sun-Yuan Hsieh, Ling-Ju Hung, Ralf Klasing, Chia-Wei Lee, Bang Ye Wu
JOURNAL OF COMPUTER AND SYSTEM SCIENCES
(2018)
Article
Computer Science, Theory & Methods
Chia-Wei Lee, Tsong-Jie Lin, Sun-Yuan Hsieh
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
(2014)
Article
Mathematics
Litao Guo, Chia-Wei Lee
Article
Computer Science, Theory & Methods
Chia-Wei Lee
THEORETICAL COMPUTER SCIENCE
(2020)
Article
Mathematics, Applied
Chia-Wei Lee, Sun-Yuan Hsieh, Shuen-Shiang Yang
DISCRETE APPLIED MATHEMATICS
(2020)
Article
Computer Science, Information Systems
Sun-Yuan Hsieh, Chia-Wei Lee, Zong-Ying Yang, Heng-Wei Wang, Jun-Han Yu, Bo-Cheng Chan, Tai-Ling Ye
Proceedings Paper
Computer Science, Theory & Methods
Li-Hsuan Chen, Sun-Yuan Hsieh, Ling-Ju Hung, Ralf Klasing, Chia-Wei Lee, Bang Ye Wu
ALGORITHMS AND COMPLEXITY (CIAC 2017)
(2017)
Proceedings Paper
Computer Science, Theory & Methods
Li-Hsuan Chen, Dun-Wei Cheng, Sun-Yuan Hsieh, Ling-Ju Hung, Chia-Wei Lee, Bang Ye Wu
COMPUTING AND COMBINATORICS, COCOON 2016
(2016)
Article
Mathematics, Applied
Chia-Chen Wei, Sun-Yuan Hsieh, Chia-Wei Lee, Sheng-Lung Peng
JOURNAL OF DISCRETE ALGORITHMS
(2015)
Article
Communication
Che-Nan Kuo, Chia-Wei Lee, Nai-Wen Chang, Kuang-Husn Shih
INTERNATIONAL JOURNAL OF MOBILE COMMUNICATIONS
(2014)
Article
Computer Science, Theory & Methods
S. G. Solodky, S. A. Stasyuk
Summary: The problem of numerical differentiation for periodic functions with finite smoothness is examined. Various truncation methods are developed for multivariate functions and their approximation properties are determined. Based on these findings, sharp bounds in terms of power scale are derived for the minimum radius of Galerkin information for the studied problem.
JOURNAL OF COMPLEXITY
(2024)
Article
Computer Science, Theory & Methods
Turgay Bayraktar, Ali Ulas Ozgur Kisisel
Summary: We calculate the expected multivolume of a random half-dimensional complete intersection in CP2n and give a relative generalization of our result to the toric case.
JOURNAL OF COMPLEXITY
(2024)
Article
Computer Science, Theory & Methods
Qamrul Hasan Ansari, Moin Uddin, Jen-Chih Yao
Summary: This paper considers convex composite optimization problems on Riemannian manifolds. The semi-local convergence of the Gauss-Newton method is discussed under various conditions.
JOURNAL OF COMPLEXITY
(2024)
Article
Computer Science, Theory & Methods
Tim Johnston, Sotirios Sabanis
Summary: Tamed schemes have become an important technique for simulating SDEs and SPDEs with superlinear growth in recent years. However, the existing taming methods do not preserve the monotonicity of the coefficients. This article proposes a novel and explicit method for truncating monotonic functions, which can be used to define a polygonal (tamed) Euler scheme in finite dimensional space while preserving the monotonicity of the drift coefficient and achieving the same convergence rate as the classical Euler scheme for Lipschitz coefficients.
JOURNAL OF COMPLEXITY
(2024)
Article
Computer Science, Theory & Methods
Jiaxin Geng, Heping Wang
Summary: This paper studies multivariate approximation of periodic functions with the error measured in the L & INFIN; norm. Algorithms using function values or general linear information are considered. Equivalences of various notions of algebraic and exponential tractability are investigated under different error criteria, showing that the power of function values and general linear information is the same. The results can be applied to weighted Korobov spaces and Korobov spaces with exponential weights, providing a special solution to Open Problem 145.
JOURNAL OF COMPLEXITY
(2024)
