Search

This paper constructs an interval partition linearization algorithm for solving minimax linear fractional programming (MLFP) problem. In this algorithm, MLFP is converted and decomposed into a series of linear programs by dividing the outer 1-dimensional space of the equivalent problem (EP) into polynomially countable intervals. To improve the computational efficiency of the algorithm, two new acceleration techniques are introduced, in which the regions in outer space where the optimal solution of EP does not exist are largely deleted. In addition, the global convergence of the proposed algorithm is summarized, and its computational complexity is illustrated to reveal that it is a fully polynomial time approximation scheme. Finally, the numerical results demonstrate that the proposed algorithm is feasible and effective. [ABSTRACT FROM AUTHOR]

This paper considers several two-machine open shop problems with two agents. Each agent has an independent set of nonpreemptive jobs, and the objective is to find either a schedule minimizing a linear combination of the makespans of both agents, a schedule minimizing the makespan of one agent with the makespan of the other agent not exceeding a threshold, or all Pareto-optimal schedules with respect to the makespans of both agents. We present a number of results for the problems above, including a polynomial algorithm and a pseudo-polynomial algorithm for special cases, non-approximability, two approximation algorithms, and a fully polynomial-time approximation scheme. Finally, we run numerical experiments to show the effectiveness of the pseudo-polynomial algorithm and the approximation algorithms. [ABSTRACT FROM AUTHOR]

Several studies have reported methods for capturing ground reaction forces in the field. However, these forces are usually measured indirectly with non-interpretable "black box" models. Here we report an interpretable model with a function approximation algorithm. The model uses time series of plantar pressure from instrumented insoles to estimate vertical ground reaction forces. The study included data from 16 persons moving at different speeds on a two-belt treadmill equipped with force plates. The introduced regression model, based on a high-dimensional approximation, using only low-dimensional variable interactions, demonstrated its ability to estimate vertical ground reaction forces. The normalized mean square error for velocities between 3 and 9 km h - 1 ranged from 10.6 to 24.4 % . The accuracy of the presented approach, which can be used to analyze and interpret the learned model, was comparable to that reported in the literature. Furthermore, the evaluation of the learned model is particularly suitable for embedded and portable systems and, after a one-time calibration measurement, allows permanent and laboratory-independent measurement of vertical ground reaction forces. [ABSTRACT FROM AUTHOR]

We consider the robust version of the classic k-center clustering problem, where we wish to remove up to z points (outliers), so as to be able to cluster the remaining points in k clusters with minimum maximum radius. We study such a problem under the fully dynamic adversarial model, where points can be inserted or deleted arbitrarily. In this setting, the main goal is to design algorithms that maintain a high quality solution at any point in time, while requiring a "small" amortized cost, i.e. a "small" number of operations per insertion or deletion, on average. In our work, we provide the first constant bi-criteria approximation algorithm for such a problem with its amortized cost being independent of both z and the size of the current input. We also complement our positive result with a lower bound showing that any constant (non bi-criteria) approximation algorithm has amortized cost at least linear in z. Finally, we conduct an in-depth experimental analysis of our algorithm on Twitter, Flickr, and Air-Quality datasets showing the effectiveness of our approach. [ABSTRACT FROM AUTHOR]

We prove that Simulated Annealing with an appropriate cooling schedule computes arbitrarily tight constant-factor approximations to the minimum spanning tree problem in polynomial time. This result was conjectured by Wegener (Automata, Languages and Programming, ICALP, Berlin, 2005). More precisely, denoting by n , m , w max , and w min the number of vertices and edges as well as the maximum and minimum edge weight of the MST instance, we prove that simulated annealing with initial temperature T 0 ≥ w max and multiplicative cooling schedule with factor 1 - 1 / ℓ , where ℓ = ω (m n ln (m)) , with probability at least 1 - 1 / m computes in time O (ℓ (ln ln (ℓ) + ln (T 0 / w min))) a spanning tree with weight at most 1 + κ times the optimum weight, where 1 + κ = (1 + o (1)) ln (ℓ m) ln (ℓ) - ln (m n ln (m)) . Consequently, for any ϵ > 0 , we can choose ℓ in such a way that a (1 + ϵ) -approximation is found in time O ((m n ln (n)) 1 + 1 / ϵ + o (1) (ln ln n + ln (T 0 / w min))) with probability at least 1 - 1 / m . In the special case of so-called (1 + ϵ) -separated weights, this algorithm computes an optimal solution (again in time O ((m n ln (n)) 1 + 1 / ϵ + o (1) (ln ln n + ln (T 0 / w min))) ), which is a significant speed-up over Wegener's runtime guarantee of O (m 8 + 8 / ϵ) . Our tighter upper bound also admits the result that in some situations a hybridization of simulated annealing and the (1 + 1) EA can lead to stronger runtime guarantees than either algorithm alone. [ABSTRACT FROM AUTHOR]

We initiate the work on maximin share (MMS) fair allocation of m indivisible chores to n agents using only their ordinal preferences, from both algorithmic and mechanism design perspectives. The previous best-known approximation ratio using ordinal preferences is 2 - 1 / n by Aziz et al. [AAAI 2017]. We improve this result by giving a deterministic 5/3-approximation algorithm that determines an allocation sequence of agents, according to which items are allocated one by one. By a tighter analysis, we show that for n = 2 and 3, our algorithm achieves better approximation ratios, and is actually optimal. We also consider the setting with strategic agents, where agents may misreport their preferences to manipulate the outcome. We first provide a strategyproof O (log (m / n)) -approximation consecutive picking algorithm, and then improve the approximation ratio to O (log n) by a randomized algorithm. Both algorithms only use the ordinal preferences of agents. Our results uncover some interesting contrasts between the approximation ratios achieved for chores versus goods. [ABSTRACT FROM AUTHOR]

We study the D-optimal Data Fusion (DDF) problem, which aims to select new data points, given an existing Fisher information matrix, so as to maximize the logarithm of the determinant of the overall Fisher information matrix. We show that the DDF problem is NP-hard and has no constant-factor polynomial-time approximation algorithm unless P = NP. Therefore, to solve the DDF problem effectively, we propose two convex integer-programming formulations and investigate their corresponding complementary and Lagrangian-dual problems. Leveraging the concavity of the objective functions in the two proposed convex integer-programming formulations, we design an exact algorithm, aimed at solving the DDF problem to optimality. We further derive a family of submodular valid inequalities and optimality cuts, which can significantly enhance the algorithm performance. We also develop scalable randomized-sampling and local-search algorithms with provable performance guarantees. Finally, we test our algorithms using real-world data on the new phasor-measurement-units placement problem for modern power grids, considering the existing conventional sensors. Our numerical study demonstrates the efficiency of our exact algorithm and the scalability and high-quality outputs of our approximation algorithms. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: Y. Li and W. Xie were supported in part by Division of Civil, Mechanical and Manufacturing Innovation [Grant 2046414] and Division of Computing and Communication Foundations [Grant 2246417]. J. Lee was supported in part by Air Force Office of Scientific Research [Grants FA9550-19-1-0175 and FA9550-22-1-0172]. M. Fampa was supported in part by Conselho Nacional de Desenvolvimento Científico e Tecnológico [Grants 305444/2019-0 and 434683/2018-3]. F. Qiu and R. Yao were supported in part by the U.S. Department of Energy Advanced Grid Modeling Program under [Grant DE-OE0000875]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2022.0235. [ABSTRACT FROM AUTHOR]

This study considers a well-known critical node detection problem that aims to minimize a pairwise connectivity measure of an undirected graph via the removal of a subset of nodes (referred to as critical nodes) subject to a cardinality constraint. Potential applications include epidemic control, emergency response, vulnerability assessment, carbon emission monitoring, network security, and drug design. To solve the problem, we present a "reduce-solve-combine" memetic search approach that integrates a problem reduction mechanism into the popular population-based memetic algorithm framework. At each generation, a common pattern mined from two parent solutions is first used to reduce the given problem instance, then the reduced instance is solved by a component-based hybrid neighborhood search that effectively combines an articulation point impact strategy and a node weighting strategy, and finally an offspring solution is produced by combining the mined common pattern and the solution of the reduced instance. Extensive evaluations on 42 real-world and synthetic benchmark instances show the efficacy of the proposed method, which discovers nine new upper bounds and significantly outperforms the current state-of-the-art algorithms. Investigation of key algorithmic modules additionally discloses the importance of the proposed ideas and strategies. Finally, we demonstrate the generality of the proposed method via its adaptation to solve the node-weighted critical node problem. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported by the National Natural Science Foundation of China [Grants 72371157, 61903144, 72031007]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0130) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0130). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

We study the NP-complete Maximum Outerplanar Subgraph problem. The previous best known approximation ratio for this problem is 2 / 3. We propose a new approximation algorithm which improves the ratio to 7 / 10. [ABSTRACT FROM AUTHOR]

Analytical solutions are practical tools in ocean engineering, but their derivation is often constrained by the complexities of the real world. This underscores the necessity for alternative approaches. In this study, the potential of Physics-Informed Neural Networks (PINN) for solving the one-dimensional vertical suspended sediment mixing (settling-diffusion) equation which involves simplified and arbitrary vertical Ds profiles is explored. A new approach of temporal Normalized Physics-Informed Neural Networks (T-NPINN), which normalizes the time component is proposed, and it achieves a remarkable accuracy (Mean Square Error of 10 − 5 and Relative Error Loss of 10 − 4 ). T-NPINN also proves its ability to handle the challenges posed by long-duration spatiotemporal models, which is a formidable task for conventional PINN methods. In addition, the T-NPINN is free of the limitations of numerical methods, e.g., the susceptibility to inaccuracies stemming from the discretization and approximations intrinsic to their algorithms, particularly evident within intricate and dynamic oceanic environments. The demonstrated accuracy and versatility of T-NPINN make it a compelling complement to numerical techniques, effectively bridging the gap between analytical and numerical approaches and enriching the toolkit available for oceanic research and engineering. [ABSTRACT FROM AUTHOR]

Submodular maximization is a NP-hard combinatorial optimization problem regularly used in machine learning and data mining with large-scale data sets. To quantify the running time of approximation algorithms, the query complexity and adaptive complexity are two important measures, where the adaptivity of an algorithm is the number of sequential rounds it makes when each round can execute polynomially many function evaluations in parallel. These two concepts reasonably quantify the efficiency and practicability of parallel computation. In this paper, we consider the problem of maximizing a nonnegative monotone DR-submodular function over a bounded integer lattice with a cardinality constraint in a value oracle model. Prior to our work, Soma and Yoshida (Math Program 172:539–563, 2018) have studied this problem and present an approximation algorithm with almost optimal approximate ratio and the same adaptivity and query complexity. We develop two novel algorithms, called low query algorithm and low adaptivity algorithm, which have approximation ratios equal to Soma and Yoshida (2018), but reach a new record of query complexity and adaptivity. As for methods, compared with the threshold greedy in Soma and Yoshida (2018), the low query algorithm reduces the number of possible thresholds and improves both the adaptivity and query complexity. The low adaptivity algorithm further integrates a vector sequencing technique to accelerate adaptive complexity in an exponential manner while only making logarithmic sacrifices on oracle queries. [ABSTRACT FROM AUTHOR]

A dominator coloring of a graph G is a proper vertex coloring with a domination property that each vertex dominates a color class. The minimum number of colors used in a dominator coloring of G is called dominator chromatic number of G and is denoted as χ d (G). Graphs with χ d (G) ≤ 3 have characterizations and such graphs can be recognized in polynomial time. However, for k ≥ 4 , deciding whether χ d (G) ≤ k is NP-hard. In this paper, we investigate the computational complexity of minimum q -dominator partization problem (Min- q -D-Partz). In Min- q -D-Partz, given a graph G , the objective is to find a vertex set S of minimum size such that χ d (G [ V ∖ S ]) ≤ q. We prove that Min- 2 -D-Partz is APX-complete and has a two-factor approximation algorithm. We also prove that Min- 3 -D-Partz cannot be approximated within any constant factor and can be approximated within a factor of O (log n). [ABSTRACT FROM AUTHOR]

Over the past few decades, there has been a significant increase in the number of Earth observation satellites, and the area of ground targets requiring observation has also been expanding. To effectively utilize the capabilities of these satellites and capture larger areas of ground targets, it has become essential to plan imaging tasks for large regional coverage using multiple satellites. First, we establish a 0-1 integer programming model to accurately describe the problem and analyze the challenges associated with solving the model. Second, we propose a heuristic algorithm based on the triple grids method. This approach utilizes a generated grid to create fewer candidate strips, a calculation grid to determine the effective coverage area more accurately, and a refined grid to solve the issue of repeated coverage of strips. Furthermore, we employ an approximation algorithm to further improve the solutions obtained from the heuristic algorithm. By comparing the proposed method to the traditional greedy heuristic algorithm and three evolutionary algorithms, the results show that our method has better performance in terms of coverage and efficiency. [ABSTRACT FROM AUTHOR]

The present work is devoted to the eigenvalue asymptotic expansion of the Toeplitz matrix Tn(a), whose generating function a is complex-valued and has a power singularity at one point. As a consequence, Tn(a) is non-Hermitian and we know that in this setting, the eigenvalue computation is a nontrivial task for large sizes. First we follow the work of Bogoya, Böttcher, Grudsky, and Maximenko and deduce a complete asymptotic expansion for the eigenvalues. In a second step, we apply matrixless algorithms, in the spirit of the work by Ekström, Furci, Garoni, Serra-Capizzano et al., for computing those eigenvalues. Since the inner and extreme eigenvalues have different asymptotic behaviors, we worked on them independently and combined the results to produce a high precision global numerical and matrixless algorithm. The numerical results are very precise, and the computational cost of the proposed algorithms is independent of the size of the considered matrices for each eigenvalue, which implies a linear cost when the entire spectrum is computed. From the viewpoint of real-world applications, we emphasize that the class under consideration includes the matrices stemming from the numerical approximation of fractional diffusion equations. In the final section a concise discussion on the matter and a few open problems are presented. [ABSTRACT FROM AUTHOR]

This study addresses the energy efficiency challenge in cloud data centers by examining the Virtual Machine Placement (VMP) problem. VMP involves mapping virtual machines (VMs) to physical machines (PMs) under capacity constraints. The paper focuses on the bin packing with linear usage cost (BPLUC) variant of bin packing, which includes fixed and variable costs in the calculation of the cost of a used bin. We prove that every approximation algorithm for the bin and vector bin packing can be used for BPLUC and VBPLUC, respectively. We propose a more power-efficient approach to VMP by applying a vector bin packing algorithm to minimize power consumption in data centers. We test the proposed algorithm on various synthetic and real workloads, and the experimental results demonstrate that it is more power-efficient than existing algorithms for VMP. The findings suggest that the proposed algorithm has significant implications for energy-efficient strategies in cloud data centers. Generally, this study makes contributes to the development of energy-efficient approaches to VMP that can help reduce power consumption and improve the sustainability of cloud data centers. [ABSTRACT FROM AUTHOR]

• A frequency-domain retracker with interface to In-Flight Point-Target-Response. • Assessment of the impact of In-Flight Point-Target-Response for Sentinel-6 MF. • The range walk correction applied via a Chirp-Zeta-Transform algorithm. • Assessment of the impact of the range-walk correction for Sentinel-6 MF. • A full Cal/Val of the first year of Sentinel-6 MF altimetry science data. Poseidon-4 is a dual-frequency redundant radar altimeter on board the European Commission Copernicus Programme Sentinel-6 Michael Freilich satellite, that represents a significant breakthrough with respect to its predecessors Jason-class altimeters due to its digital architecture and to its innovative measurements and calibration modes. In the framework of the Sentinel-6 Michael Freilich commissioning preparatory activities, CNES has contracted CLS for the development of a Sentinel-6 Processing Prototype (S6PP) application. S6PP is a multi-chain processing suite able to process Sentinel-6 Level-1A and Level-1B data products up to Level-2. The novel algorithms developed in the CNES/CLS research and development activities are implemented within S6PP and validated to support the different thematic applications (in particular inland water and ocean) and in view of promoting them for possible implementation in the operational ground segment. The present work covers in particular the main results over open ocean for the main altimetric geophysical variables over the sea surface (sea surface height anomaly, significant wave-height, sigma-nought and wind speed) derived by the Low-Resolution Mode (LRM) and High-Resolution Mode (HRM) chains of S6PP in terms of precision, accuracy, spectral content and measurement stability. Given the reported variation of the payload in-orbit temperatures along with the reported instrumental ageing, and given the tight requirement to measure the GMSL (Global Mean Sea Level) in seamless continuity with Jason-3, the clear goal for S6PP was to process the S6-MF data with the minimum possible level of approximations along the processing pipeline but still maintaining a very efficient prototype from the computational point of view. For this scope, a novel and computationally efficient numerical retracking scheme with interface to the in-flight PTR (Point Target Response) provided by the instrument calibration chain has been put in place within S6PP for both the Low-Resolution and High-Resolution modes whereas the Delay-Doppler beam-forming is carried out by applying the range walk correction based on a computationally efficient algorithm (Chirp Zeta-Transform). The impact of the range walk correction and of the in-flight PTR interface is assessed for HRM and LRM, respectively. The paper shows that the proposed processing baseline ensures a dataset robust from the currently known instrumental degradation or ageing issues, both in LRM and HRM mode and, once this is done, that Sentinel-6 Michael Freilich global mean sea level measurement is in line with the one measured by Jason-3. [ABSTRACT FROM AUTHOR]

In this article, we consider the rank‐structured approximation of one important type of Cauchy matrix. This approximation plays a key role in some structured matrix methods such as stable and efficient direct solvers and other algorithms for Toeplitz matrices and certain kernel matrices. Previous rank‐structured approximations (specifically hierarchically semiseparable, or HSS, approximations) for such a matrix of size n$$ n $$ cost at least O(n)$$ O(n) $$ complexity. Here, we show how to construct an HSS approximation with sublinear (specifically, O(log3n)$$ O\left({\log}^3n\right) $$) complexity. The main ideas include extensive computation reuse and an analytical far‐field compression strategy. Low‐rank compression at each hierarchical level is restricted to just a single off‐diagonal block row, and a resulting basis matrix is then reused for other off‐diagonal block rows as well as off‐diagonal block columns. The relationships among the off‐diagonal blocks are rigorously analyzed. The far‐field compression uses an analytical proxy point method where we optimize the choice of some parameters so as to obtain accurate low‐rank approximations. Both the basis reuse ideas and the resulting analytical hierarchical compression scheme can be generalized to some other kernel matrices and are useful for accelerating relevant rank‐structured approximations (though not subsequent operations like matrix‐vector multiplications). [ABSTRACT FROM AUTHOR]

Randomized matrix algorithms have become workhorse tools in scientific computing and machine learning. To use these algorithms safely in applications, they should be coupled with posterior error estimates to assess the quality of the output. To meet this need, this paper proposes two diagnostics: a leave-one-out error estimator for randomized low-rank approximations and a jackknife resampling method to estimate the variance of the output of a randomized matrix computation. Both of these diagnostics are rapid to compute for randomized low-rank approximation algorithms such as the randomized SVD and randomized Nystr\"om approximation, and they provide useful information that can be used to assess the quality of the computed output and guide algorithmic parameter choices. [ABSTRACT FROM AUTHOR]

Given a metric space \scrM = (X, γ), a weighted graph G over X is a metric t-spanner of scrM if for every u, v \in X, γ(u, v) \leq γG(u, v) \leq t \cdot γ (u, v), where γ G is the shortest path metric in G. In this paper, we construct spanners for finite sets in metric spaces in the online setting. Here, we are given a sequence of points (s1,. . ., sn), where the points are presented one at a time (i.e., after i steps, we see Si = \{ s1, . . ., si\}). The algorithm is allowed to add edges to the spanner when a new point arrives; however, it is not allowed to remove any edge from the spanner. The goal is to maintain a t-spanner Gi for Si for all i, while minimizing the number of edges, and their total weight. We construct online (1+ε)-spanners in the Euclidean d-space, (2k 1)(1+ε)-spanners for general metrics, and (2 + ε)-spanners for ultrametrics. Most notably, in the Euclidean plane, we construct a (1 + ε)-spanner with competitive ratio O(\varepsilon 3/2 log n 1 log n), bypassing the classic lower bound (ε 2) for lightness, which compares the weight of the spanner to that of the minimum spanning tree. [ABSTRACT FROM AUTHOR]

Since the seminal result of Karger, Motwani, and Sudan, algorithms for approximate 3-coloring have primarily centered around rounding the solution to a Semidefinite Program. However, it is likely that important combinatorial or algebraic insights are needed in order to break the no(1) threshold. One way to develop new understanding in graph coloring is to study special subclasses of graphs. For instance, Blum studied the 3-coloring of random graphs, and Arora and Ge studied the 3-coloring of graphs with low threshold-rank. In this work, we study graphs that arise from a tensor product, which appear to be novel instances of the 3-coloring problem. We consider graphs of the form H = (V,E) with V = V (K3 G) and E = E(K3 G) s E, where E E(K3 G) is any edge set such that no vertex has more than an -fraction of its edges in E. We show that one can construct H = K3 \times G with V (H) = V (H) that is close to H. For arbitrary G, H satisfies | E(H)Δ E H)| O(\epsilon | E(H)|). Additionally, when G is a mild expander, we provide a 3-coloring for H in polynomial time. These results partially generalize an exact tensor factorization algorithm of Imrich. On the other hand, without any assumptions on G, we show that it is NP-hard to 3-color H. [ABSTRACT FROM AUTHOR]

Let P be a set of points in Rd, where each point p ∈ P has an associated transmission range, denoted (p). The range assignment induces a directed communication graph Gp (P) on P, which contains an edge (p, q) iff | pq| (p). In the broadcast range-assignment problem, the goal is to assign the ranges such that (P) contains an arborescence rooted at a designated root node and the costΣp∈ P(p)² of the assignment is minimized. We study the dynamic version of this problem. In particular, we study trade-offs between the stability of the solution-the number of ranges that are modified when a point is inserted into or deleted from P-and its approximation ratio. To this end we study k-stable algorithms, which are algorithms that modify the range of at most k points when they update the solution. We also introduce the concept of a stable approximation scheme, or SAS for short. A SAS is an update algorithm \mathrm{A}\mathrm{L}\mathrm{G} that, for any given fixed parameter ε >0, is kε-stable and that maintains a solution with approximation ratio 1 + \ε, where the stability parameter k(\varepsilon) only depends on ε and not on the size of P. We study such trade-offs in three settings. (1) For the problem in R¹, we present a SAS with kε = O(1/ε. Furthermore, we prove that this is tight in the worst case: any SAS for the problem must have kε =ε (1ε). We also present 1-, 2-, and 3-stable algorithms with constant approximation ratio. (2) For the problem in S1 (that is, when the underlying space is a circle) we prove that no SAS exists. This is in spite of the fact that, for the static problem in S1, we prove that an optimal solution can always be obtained by cutting the circle at an appropriate point and solving the resulting problem in R¹. (3) For the problem in R2, we also prove that no SAS exists, and we present a O(1)-stable O(1)-approximation algorithm. Most results γ generalize to the setting where, for any given constant α > 1, the range-assignment cost is pΣ (p)∈α. [ABSTRACT FROM AUTHOR]

We consider classes of objective functions of cardinality-constrained maximization problems for which the greedy algorithm guarantees a constant approximation. We propose the new class of γ -β -augmentable functions and prove that it encompasses several important subclasses, such as functions of bounded submodularity ratio, \alpha -augmentable functions, and weighted rank functions of an independence system of bounded rank quotient-as well as additional objective functions for which the greedy algorithm yields an approximation. For this general class of functions, we show a tight bound of α/γeα/eα-1 \mathrm{e}α 1 on the approximation ratio of the greedy algorithm that tightly interpolates between bounds from the literature for functions of bounded submodularity ratio and for α -augmentable functions. In particular, as a by-product, we close a gap in [A. Bernstein et al., Math. Program., 191 (2022), pp. 953--979] by obtaining a tight lower bound for \alpha -augmentable functions for all \α 1. For weighted rank functions of independence systems, our tight bound becomes α, which recovers the known bound of 1/q for independence systems of rank quotient at least q. [ABSTRACT FROM AUTHOR]

We consider a selection problem with stochastic probing. There is a set of items whose values are drawn from independent distributions. The distributions are known in advance. Each item can be tested repeatedly. Each test reduces the uncertainty about the realization of its value. We study a testing model, where the first test reveals whether the realized value is smaller or larger than the c-quantile of the underlying distribution of some constant c \in (0, 1). Subsequent tests allow us to further narrow down the interval in which the realization is located. There is a limited number of possible tests, and our goal is to design near-optimal testing strategies that allow us to maximize the expected value of the chosen item. We study both identical and nonidentical distributions and develop polynomial-time algorithms with constant approximation factors in both scenarios. [ABSTRACT FROM AUTHOR]

This paper introduces the d-distanceb-matching problem, in which we are given a bipartite graph G = (S , T ; E) with S = { s 1 , ⋯ , s n } , a weight function on the edges, an integer d ∈ Z + and a degree bound function b : S ∪ T → Z + . The goal is to find a maximum-weight subset M ⊆ E of the edges satisfying the following two conditions: (1) the degree of each node v ∈ S ∪ T is at most b(v) in M, (2) if s i t , s j t ∈ M , then | i - j | ≥ d . In the cyclic version of the problem, the nodes in S are considered to be in cyclic order. We get back the (cyclic)d-distance matching problem when b (s) = 1 for s ∈ S and b (t) = ∞ for t ∈ T . We prove that the d-distance matching problem is APX-hard, even in the unweighted case. We show that 2 - 1 d is a tight upper bound on the integrality gap of the natural integer programming model for the cyclic d-distance b-matching problem provided that (2 d - 1) divides the size of S. For the non-cyclic case, the integrality gap is shown to be at most (2 - 2 d) . The proofs give approximation algorithms with guarantees matching these bounds, and also improve the best known algorithms for the (cyclic) d-distance matching problem. In a related problem, our goal is to find a permutation of S maximizing the weight of the optimal d-distance b-matching. This problem can be solved in polynomial time for the (cyclic) d-distance matching problem — even though the (cyclic) d-distance matching problem itself is NP-hard and also hard to approximate arbitrarily. For (cyclic) d-distance b-matchings, however, we prove that finding the best permutation is NP-hard, even if b ≡ 2 or d = 2 , and we give e-approximation algorithms. [ABSTRACT FROM AUTHOR]

A Roman dominating function (RDF) of a graph G = (V , E) is a function f : V → { 0 , 1 , 2 } such that every vertex assigned the value 0 is adjacent to a vertex assigned the value 2. A global Roman dominating function (GRDF) of a graph G = (V , E) is a function f : V → { 0 , 1 , 2 } such that f is a Roman dominating function of both G and its complement G ¯. The weight of f is f (V) = Σ u ∈ V f (u). The minimum weight of a GRDF in a graph G is known as global Roman domination number of G and is denoted by γ g R (G). Minimum Global Roman Domination is to find a global Roman dominating function of minimum weight and Decide Global Roman Domination is the decision version of Minimum Global Roman Domination. In this paper, we show that Decide Global Roman Domination is NP -complete for bipartite graphs and chordal graphs. On the positive side, we give a polynomial-time algorithm for Minimum Global Roman Domination for threshold graphs. Further, we propose an O (ln | V |) -approximation algorithm for Minimum Global Roman Domination for a graph G = (V , E). We also show that Minimum Global Roman Domination cannot be approximated within a factor of (1 − ϵ) ln | V | for any ϵ > 0 unless P = NP. Next, we show that Minimum Global Roman Domination admits a constant approximation algorithm for bounded degree graphs. Finally, we show that Minimum Global Roman Domination is APX -complete for bounded degree graphs. [ABSTRACT FROM AUTHOR]

For a connected graph G = (V , E) , a function r i : V ↦ { 0 , 1 , 2 } is an Italian dominating function (IDF) if every vertex v with r i (v) = 0 is either adjacent to a vertex u with r i (u) = 2 or adjacent to at least two vertices x , y with r i (x) = r i (y) = 1. The weight of r i is ∑ v ∈ V r i (v) and the minimum Italian dominating function problem (MinIDF) is to compute an IDF with minimum weight. The minimum connected Italian dominating function problem (MinCIDF) is to find a minimum weight IDF r c i such that the subgraph of G induced by vertex set { v ∈ V ∣ r c i (v) = 1 or r c i (v) = 2 } is connected. In this paper, we give a greedy algorithm for the MinIDF problem with approximation ratio at most 2 + ln (1 2 Δ + 1) , and a greedy algorithm for the MinCIDF problem with approximation ratio at most 4 + ln (1 2 Δ − 1) , where Δ is the maximum degree of the graph. [ABSTRACT FROM AUTHOR]

The length of a tree-decomposition of a graph is the maximum distance (in the graph) between two vertices of a same bag of the decomposition. The treelength of a graph is the minimum length among its tree-decompositions. Treelength of graphs has been studied for its algorithmic applications in classical metric problems such as Traveling Salesman Problem or metric dimension of graphs and also, in compact routing in the context of distributed computing. Deciding whether the treelength of a general graph is at most 2 is NP-complete (graphs of treelength one are precisely the chordal graphs), and it is known that the treelength of a graph cannot be approximated up to a factor less than 3 2 (the best known approximation algorithm for treelength has an approximation ratio of 3). However, nothing is known on the computational complexity of treelength in planar graphs, except that the treelength of any outerplanar graph is equal to the third of the size of a largest isometric cycle. This work initiates the study of treelength in planar graphs by considering the next natural subclass of planar graphs, namely the one of series–parallel graphs. We first fully describe the treelength of melon graphs (set of pairwise internally disjoint paths linking two vertices), showing that, even in such a restricted graph class, the expression of the treelength is not trivial. Then, we show that treelength can be approximated up to a factor 3 2 in series–parallel graphs. Our main result is a quadratic-time algorithm for deciding whether a series–parallel graph has treelength at most 2. Our latter result relies on a characterization of series–parallel graphs with treelength 2 in terms of an infinite family of forbidden isometric subgraphs. [ABSTRACT FROM AUTHOR]

Given a graph G = (V , E) , an L (2 , 1) -labeling of the graph is an assignment ℓ from the vertex set to the set of nonnegative integers such that for any pair of vertices (u , v) , | ℓ (u) − ℓ (v) | ≥ 2 if u and v are adjacent, and ℓ (u) ≠ ℓ (v) if u and v are at distance 2. The L (2 , 1) -labeling problem is to minimize the range of ℓ (i.e., max u ∈ V (ℓ (u)) − min u ∈ V (ℓ (u)) + 1). Although the problem is generally hard to approximate within any constant factor, it was known to be approximable within factor 10.67 for unit disk graphs. This paper designs a new way of partitioning the plane into squares for periodic labeling, based on which we present an 8-approximation polynomial-time algorithm for L (2 , 1) -labeling of unit disk graphs. • An 8-approximation algorithm of L(2,1)-labeling for unit disk graphs with geometric representations is presented. • The previously known bound is 10.67. • The presented algorithm gives a simple periodic labeling based on a new way of partitioning the plane into squares. [ABSTRACT FROM AUTHOR]

An algorithm for automatic approximation of the time dependence x(t) is built for the observed coordinate of the coronal mass ejection (CME) front from the admissible starting point to the first appearance in the field of view of the LASCO coronagraph and further, up to a heliocentric distance of ~25 solar radii (RS). In the region from the starting point to the first appearance of the CME, two sections are assumed, with uniform (impulsive) acceleration and with uniform motion; then, the motion is approximated by observations. At the beginning of the approximation, either the CME start time is found through the appearance of certain frequencies of radio emissions (RSTN data) and type II and IV radio emissions (sequence characteristics are determined by machine learning), or the start time is determined by averaging over the allowable takeoff area; then the polynomial-ballistic model is optimized. The first and second derivatives x(t) determine the speed and acceleration of the CME at any point of its trajectory. Such an algorithm is necessary to obtain the most accurate kinematic characteristics of CMEs, which can allow one to study the physical, spatial, and temporal relationships between flares and CMEs in all their diversity. Widely used approximation techniques simplify the real CME trajectories x(t), thereby possibly discarding important features of the CME kinematics and flare development in the posteruptive phase. The algorithm was trained and tested on 17 solar flares and associated CMEs, which are known for their powerful proton events with proton energies greater than 300 MeV. The rate of the first occurrence of CMEs turned out to be different from the average rate given in the LASCO catalog, which is important for estimating the energy of flares and CMEs. In 7 out of 17 events, there was acceleration only in the impulsive phase (and then deceleration), while acceleration in the impulsive and posteruptive phases occurred in 10 events. In 4 out of 17 events, CME velocities greater than 2000 km/s were reached at a distance of 20RS. The accuracy of determining the kinematic characteristics of CMEs can be improved by using additional observations, for example, SDO AIA in the September 10, 2017 event. [ABSTRACT FROM AUTHOR]

The gate-based model is one of the leading quantum computing paradigms for representing quantum circuits. Within this paradigm, a quantum algorithm is expressed in terms of a set of quantum gates that are executed on the quantum hardware over time, subject to a number of constraints whose satisfaction must be guaranteed before running the circuit, to allow for feasible execution. The need to guarantee the previous feasibility condition gives rise to the Quantum Circuit Compilation Problem (QCCP). The QCCP has been demonstrated to be NP-Complete, and can be considered as a Planning and Scheduling problem. In this paper, we consider quantum compilation instances deriving from the general Quantum Approximation Optimization Algorithm (QAOA), applied to the MaxCut problem, devised to be executed on Noisy Intermediate Scale Quantum (NISQ) hardware architectures. More specifically, in addition to the basic QCCP version, we also tackle other variants of the same problem such as the QCCP-X (QCCP with crosstalk constraints), the QCCP-V (QCCP with variable qubit state initialization), as well as the QCCP-VX that includes both previous variants. All problem variants are solved using genetic algorithms. We perform an experimental study across a conventional set of instances taken from the literature, and show that the proposed genetic algorithm, termed G A VX , outperforms previous approaches in the literature. [ABSTRACT FROM AUTHOR]

Simple heuristics for (combinatorial) optimization problems often show a remarkable performance in practice. Worst-case analysis often falls short of explaining this performance. Because of this, "beyond worst-case analysis" of algorithms has recently gained a lot of attention, including probabilistic analysis of algorithms. The instances of many (combinatorial) optimization problems are essentially a discrete metric space. Probabilistic analysis for such metric optimization problems has nevertheless mostly been conducted on instances drawn from Euclidean space, which provides a structure that is usually heavily exploited in the analysis. However, most instances from practice are not Euclidean. Little work has been done on metric instances drawn from other, more realistic, distributions. Some initial results have been obtained in recent years, where random shortest path metrics generated from dense graphs (either complete graphs or Erdős–Rényi random graphs) have been used so far. In this paper we extend these findings to sparse graphs, with a focus on sparse graphs with 'fast growing cut sizes', i.e. graphs for which | δ (U) | = Ω (| U | ε) for some constant ε ∈ (0 , 1) for all subsets U of the vertices, where δ (U) is the set of edges connecting U to the remaining vertices. A random shortest path metric is constructed by drawing independent random edge weights for each edge in the graph and setting the distance between every pair of vertices to the length of a shortest path between them with respect to the drawn weights. For such instances generated from a sparse graph with fast growing cut sizes, we prove that the greedy heuristic for the minimum distance maximum matching problem, and the nearest neighbor and insertion heuristics for the traveling salesman problem all achieve a constant expected approximation ratio. Additionally, for instances generated from an arbitrary sparse graph, we show that the 2-opt heuristic for the traveling salesman problem also achieves a constant expected approximation ratio. [ABSTRACT FROM AUTHOR]

We study the Non-preemptive Peak Demand Minimization (NPDM) problem, where we are given a set of jobs, specified by their processing times and energy requirements. The goal is to schedule all jobs within a fixed time period such that the peak load (the maximum total energy requirement at any time) is minimized. This problem has recently received significant attention due to its relevance in smart-grids. Theoretically, the problem is related to the classical strip packing problem (SP). In SP, a given set of axis-aligned rectangles must be packed into a fixed-width strip, such that the height of the strip is minimized. NPDM can be modeled as strip packing with slicing and stacking constraint: each rectangle may be cut vertically into multiple slices and the slices may be packed into the strip as individual pieces. The stacking constraint forbids solutions where two slices of the same rectangle are intersected by the same vertical line. Non-preemption enforces the slices to be placed in contiguous horizontal locations (but may be placed at different vertical locations). We obtain a (5 / 3 + ε) -approximation algorithm for the problem. We also provide an asymptotic efficient polynomial-time approximation scheme (AEPTAS) which generates a schedule for almost all jobs with energy consumption (1 + ε) OPT . The remaining jobs fit into a thin container of height 1. This AEPTAS is used as a subroutine to acquire the (5 / 3 + ε) -approximation algorithm. The previous best result for NPDM was a 2.7-approximation based on FFDH (Ranjan et al., in: 2015 IEEE symposium on computers and communication (ISCC), pp 758–763, IEEE, 2015). One of our key ideas is providing several new lower bounds on the optimal solution of a geometric packing, which could be useful in other related problems. These lower bounds help us to obtain approximative solutions based on Steinberg's algorithm in many cases. In addition, we show how to split schedules generated by the AEPTAS into few segments and to rearrange the corresponding jobs to insert the thin container mentioned above, such that it does not exceed the bound of (5 / 3 + ε) OPT . [ABSTRACT FROM AUTHOR]

We present deterministic algorithms for maintaining a (3 / 2 + ϵ) and (2 + ϵ) -approximate maximum matching in a fully dynamic graph with worst-case update times O ^ (n) and O ~ (1) respectively. The fastest known deterministic worst-case update time algorithms for achieving approximation ratio (2 - δ) (for any δ > 0 ) and (2 + ϵ) were both shown by Roghani et al. (Beating the folklore algorithm for dynamic matching, 2021) with update times O (n 3 / 4) and O ϵ (n) respectively. We close the gap between worst-case and amortized algorithms for the two approximation ratios as the best deterministic amortized update times for the problem are O ϵ (n) and O ~ (1) which were shown in Bernstein and Stein (in: Proceedings of the twenty-seventh annual ACM-SIAM symposium on discrete algorithms, 2016) and Bhattacharya and Kiss (in: 48th international colloquium on automata, languages, and programming, ICALP 2021, 12–16 July, Glasgow, 2021) respectively. The algorithm achieving (3 / 2 + ϵ) approximation builds on the EDCS concept introduced by the influential paper of Bernstein and Stein (in: International colloquium on automata, languages, and programming, Springer, Berlin, 2015). Say that H is a (α , δ) -approximate matching sparsifier if at all times H satisfies that μ (H) · α + δ · n ≥ μ (G) (define (α , δ) -approximation similarly for matchings). We show how to maintain a locally damaged version of the EDCS which is a (3 / 2 + ϵ , δ) -approximate matching sparsifier. We further show how to reduce the maintenance of an α -approximate maximum matching to the maintenance of an (α , δ) -approximate maximum matching building based on an observation of Assadi et al. (in: Proceedings of the twenty-seventh annual (ACM-SIAM) symposium on discrete algorithms, (SODA) 2016, Arlington, VA, USA, January 10–12, 2016). Our reduction requires an update time blow-up of O ^ (1) or O ~ (1) and is deterministic or randomized against an adaptive adversary respectively. To achieve (2 + ϵ) -approximation we improve on the update time guarantee of an algorithm of Bhattacharya and Kiss (in: 48th International colloquium on automata, languages, and programming, ICALP 2021, 12–16 July, Glasgow, 2021). In order to achieve both results we explicitly state a method implicitly used in Nanongkai and Saranurak (in: Proceedings of the twenty-seventh annual ACM symposium on theory of computing, 2017) and Bernstein et al. (Fully-dynamic graph sparsifiers against an adaptive adversary, 2020) which allows to transform dynamic algorithms capable of processing the input in batches to a dynamic algorithms with worst-case update time. [ABSTRACT FROM AUTHOR]

Conceptual distance refers to the degree of proximity between two concepts within a conceptualization. It is closely related to semantic similarity and relationships, but its measurement strongly depends on the context of the given concepts. DIS-C represents an advancement in the computation of semantic similarity/relationships that is independent of the type of knowledge structure and semantic relations when generating a graph from a knowledge base (ontologies, semantic networks, and hierarchies, among others). This approach determines the semantic similarity between two indirectly connected concepts in an ontology by propagating local distances by applying an algorithm based on the All Pairs Shortest Path (APSP) problem. This process is implemented for each pair of concepts to establish the most effective and efficient paths to connect these concepts. The algorithm identifies the shortest path between concepts, which allows for an inference of the most relevant relationships between them. However, one of the critical issues with this process is computational complexity, combined with the design of APSP algorithms, such as Dijkstra, which is n 3 . This paper studies different alternatives to improve the DIS-C approach by adapting approximation algorithms, focusing on Dijkstra, pruned Dijkstra, and sketch-based methods, to compute the conceptual distance according to the need to scale DIS-C to analyze very large graphs; therefore, reducing the related computational complexity is critical. Tests were performed using different datasets to calculate the conceptual distance when using the original version of DIS-C and when using the influence area of nodes. In situations where time optimization is necessary for generating results, using the original DIS-C model is not the optimal method. Therefore, we propose a simplified version of DIS-C to calculate conceptual distances based on centrality estimation. The obtained results for the simple version of DIS-C indicated that the processing time decreased 2.381 times when compared to the original DIS-C version. Additionally, for both versions of DIS-C (normal and simple), the APSP algorithm decreased the computational cost when using a two-hop coverage-based approach. [ABSTRACT FROM AUTHOR]

We introduce a dynamical system to the problem of finding zeros of the sum of two maximally monotone operators. We investigate the existence, uniqueness and extendability of solutions to this dynamical system in a Hilbert space. We prove that the trajectories of the proposed dynamical system converge strongly to a primal–dual solution of the considered problem. Under explicit time discretization of the dynamical system we obtain the best approximation algorithm for solving coupled monotone inclusion problem. [ABSTRACT FROM AUTHOR]

In this paper, the first fixed-ratio approximation algorithms are proposed for a series of asymmetric settings of well-known combinatorial routing problems. Among them are the Steiner cycle problem, the prize-collecting traveling salesman problem, the minimum cost cycle cover problem by a bounded number of cycles, etc. Almost all of the proposed algorithms rely on original reductions of the considered problems to auxiliary instances of the asymmetric traveling salesman problem and employ the breakthrough approximation results for this problem obtained recently by O. Svensson, J. Tarnawski, L. Végh, V. Traub, and J. Vygen. On the other hand, approximation of the cycle cover problem was proved by applying a deeper extension of their approach. [ABSTRACT FROM AUTHOR]

The integrated industrial control systems require a reliable communication among each part of control systems. The limitation of network topology comprises the low latency of data transmission. The network algorithm topologies are sometimes failed to ensure the faulttolerant network design even if they offer it. Therefore, this works investigates a Node Insertion Algorithm (NIA) and Ant Colony Optimization (ACO) in order to solve the Travelling Salesman Problem (TSP) for network topologies in a communication network. The NP Non deterministic (polynomial time)-hardness based of TSP leads to the impossibility of polynomial time algorithm to solve an exponentially increasing amount of communication addresses. TSP itself is a well-known solution method known in the graph theory which is based on approximation algorithm. Therefore, this work also presents a comparison between the NIA and ACO for 200 nodes of network topologies. The results show that NIA is superior than ACO in terms of resulting ring's cost and computation duration. Three topologies are tested and it is observable that NIA requires only 14.88 seconds to finish the computation in which the resulting ring's length reaches 164019 units. Therefore, the achievement of the NIA can be applied for logical and physical nodes for a reliable connection in an industrial topology network. [ABSTRACT FROM AUTHOR]

We devise the first constant-factor approximation algorithm for finding an integral multi-commodity flow of maximum total value for instances where the supply graph together with the demand edges can be embedded on an orientable surface of bounded genus. This extends recent results for planar instances. Our techniques include an uncrossing algorithm, which is significantly more difficult than in the planar case, a partition of the cycles in the support of an LP solution into free homotopy classes, and a new rounding procedure for freely homotopic non-separating cycles. [ABSTRACT FROM AUTHOR]

We present improved algorithms for the Steiner tree problem with the minimum number of Steiner points and bounded edge length. Given n terminal points in a 2D Euclidean plane and an edge length bound, the problem asks to construct a spanning tree of n terminal points with minimal Steiner points such that every edge length of the spanning tree is within the given bound. This problem is known to be NP-hard and has practical applications such as relay node placements in wireless networks, wavelength-division multiplexing(WDM) optimal network design, and VLSI design. The best-known deterministic approximation algorithm has O(n3) running time with an approximation ratio of 3. This paper proposes an efficient approximation algorithm using the Voronoi diagram that guarantees an approximation ratio of 3 in O(n log n) time. We also present the first exact algorithm to find an optimal Steiner tree for given three terminal points in constant time. Using this exact algorithm, we improve the 3-approximation algorithm with better performance regarding the number of required Steiner points in O(n log n) time. [ABSTRACT FROM AUTHOR]

For a graph G = (V , E) , a collection P of vertex-disjoint (simple) paths is called a path cover of G if every vertex v ∈ V is contained in exactly one path of P . The Path Cover problem (PC for short) is to find a minimum cardinality path cover of G. In this paper, we introduce generalizations of PC, where each path is associated with a weight (cost or profit). Our problem, Minimum (Maximum) Weighted Path Cover [MinPC (MaxPC)], is defined as follows: Let U = { 0 , 1 , ⋯ , n - 1 } . Given a graph G = (V , E) and a weight function f : U → R ∪ { + ∞ , - ∞ } that defines a weight for each path based on its length, the objective of MinPC (MaxPC) is to find a path cover P of G such that the total weight of the paths in P is minimized (maximized). Let L be a subset of U, and P L be the set of paths such that each path is of length ℓ ∈ L . We consider Min P L PC with binary cost, i.e., the cost function is f (ℓ) = 1 if ℓ ∈ L ; otherwise, f (ℓ) = 0 . We also consider Max P L PC with f (ℓ) = ℓ + 1 , if ℓ ∈ L ; otherwise, f (ℓ) = 0 . Many well-known graph theoretic problems such as the Hamiltonian Path and the Maximum Matching problems can be modeled using Min P L PC and Max P L PC. In this paper, we first show that deciding whether Min P { 0 , 1 , 2 } PC has a 0-weight solution is NP-complete for planar bipartite graphs of maximum degree three, and consequently, (i) for any constant σ ≥ 1 , there is no polynomial-time approximation algorithm with approximation ratio σ for Min P { 0 , 1 , 2 } PC unless P = NP, and (ii) Max P { 3 , ⋯ , n - 1 } PC is NP-hard for the same graph class. Next, we present a polynomial-time algorithm for Min P { 0 , 1 , ⋯ , k } PC on graphs with bounded treewidth for a fixed k. Lastly, we present a 4-approximation algorithm for Max P { 3 , ⋯ , n - 1 } PC, which becomes a 2.5-approximation algorithm for subcubic graphs. [ABSTRACT FROM AUTHOR]

Rule acquisition is significant in real life and extensively utilized in data mining. Currently, most studies have constructed rule acquisition algorithms based on the equivalence relation. However, these algorithms need to be more suitable for dominance-based decision systems and should consider applications in multi-scale environments. In this paper, we establish the dominance relation of the single-valued neutrosophic rough set model using the ranking method with the relative distance favorable degree. We then introduce this approach into a multi-scale environment to obtain the dominance relation of the multi-scale single-valued neutrosophic rough set model, resulting in two discernibility matrices and functions. We propose the algorithm for lower approximation optimal scale reduction and further examine the method of rule acquisition based on the discernibility matrix. Finally, we apply these algorithms to four random data sets to verify their effectiveness. [ABSTRACT FROM AUTHOR]

We investigate the optimal piecewise linear interpolation of the bivariate product xy over rectangular domains. More precisely, our aim is to minimize the number of simplices in the triangulation underlying the interpolation, while respecting a prescribed approximation error. First, we show how to construct optimal triangulations consisting of up to five simplices. Using these as building blocks, we construct a triangulation scheme called crossing swords that requires at most - times the number of simplices in any optimal triangulation. In other words, we derive an approximation algorithm for the optimal triangulation problem. We also show that crossing swords yields optimal triangulations in the case that each simplex has at least one axis-parallel edge. Furthermore, we present approximation guarantees for other well-known triangulation schemes, namely for the red refinement and longest-edge bisection strategies as well as for a generalized version of K1-triangulations. Thereby, we are able to show that our novel approach dominates previous triangulation schemes from the literature, which is underlined by illustrative numerical examples. [ABSTRACT FROM AUTHOR]

In the weighted flow-time problem on a single machine, we are given a set of n jobs, where each job has a processing requirement pj, release date rj, and weight wj. The goal is to find a preemptive schedule which minimizes the sum of weighted flow-time of jobs, where the flow-time of a job is the difference between its completion time and its released date. We give the first pseudopolynomial time constant approximation algorithm for this problem. The algorithm also extends directly to the problem of minimizing the lp norm of weighted flow-times. The running time of our algorithm is polynomial in n, the number of jobs, and P, which is the ratio of the largest to the smallest processing requirement of a job. Our algorithm relies on a novel reduction of this problem to a generalization of the multicut problem on trees, which we call the Demand MultiCut problem. Even though we do not give a constant factor approximation algorithm for the Demand MultiCut problem on trees, we show that the specific instances of Demand MultiCut obtained by reduction from weighted flow-time problem instances have more structure in them, and we are able to employ techniques based on dynamic programming. Our dynamic programming algorithm relies on showing that there are near optimal solutions which have nice smoothness properties, and we exploit these properties to reduce the size of the dynamic programming table. [ABSTRACT FROM AUTHOR]

Among various variants of the traveling salesman problem (TSP), the s-t-path graph TSP has the special feature that we know the exact integrality ratio, 3 2, and an approximation algorithm matching this ratio. In this paper, we go below this threshold: we devise a polynomialtime algorithm for the s-t-path graph TSP with approximation ratio 1.497. Our algorithm can be viewed as a refinement of the 3 2 -approximation algorithm in [A. SebH o and J. Vygen, Combinatorica, 34 (2014), pp. 597--629], but we introduce several completely new techniques. These include a new type of ear-decomposition, an enhanced ear induction that reveals a novel connection to matroid union, a stronger lower bound, and a reduction of general instances to instances in which s and t have small distance (which works for general metrics). [ABSTRACT FROM AUTHOR]

Temporal graphs are graphs whose topology is subject to discrete changes over time. Given a static underlying graph G , a temporal graph is represented by assigning a set of integer time-labels to every edge e of G , indicating the discrete time steps at which e is active. We introduce and study the complexity of a natural temporal extension of the classical graph problem Maximum Matching , taking into account the dynamic nature of temporal graphs. In our problem, Maximum Temporal Matching , we are looking for the largest possible number of time-labeled edges (simply time-edges) (e , t) such that no vertex is matched more than once within any time window of Δ consecutive time slots, where Δ ∈ N is given. We prove strong computational hardness results for Maximum Temporal Matching , even for elementary cases, as well as fixed-parameter algorithms with respect to natural parameters and polynomial-time approximation algorithms. [ABSTRACT FROM AUTHOR]

Multi-h continuous phase modulation (CPM), with extremely high spectral efficiency, involves the plague of high demodulation complexity with a large number of matched filters and a complex trellis. In this paper, an efficient all-digital demodulator for multi-h continuous phase modulation (CPM) is proposed based on a low-complexity decision-directed synchronization algorithm. Based on the maximum-likelihood estimation of the carrier phase and timing errors, we propose a reduced-complexity timing error detector with linear phase approximation (LPA) to the phase of the multi-h CPM. Compared with the traditional synchronization methods, it avoids derivative matched filtering and reduces about 2/3 of matched filters. The estimated accuracy and bit error rate (BER) performance of the LPA-based synchronization algorithm have no loss, as shown by the numerical simulation. Its stability is verified by the derived S-curve. Then, the receivers with the LPA-based synchronization for the three kinds of promising multi-h CPM are implemented on a Xilinx Kintex-7 FPGA platform. The experimental results show that the onboard tested BER of the proposed design has an ignorable loss in the numerical simulation. The implementation overhead on FPGA is significantly reduced by about 27% slices, 64% DSPs, and 70% block RAMs compared with the conventional method. [ABSTRACT FROM AUTHOR]

The minimum weighted vertex cover (MWVC) problem is to find a subset of vertices that can cover all the edges of the network and minimize the sum of the vertex weights in the vertex subset. MWVC is a generalization of the minimum vertex cover (MVC) problem and can be regarded as a combinatorial optimization problem. This paper proposes an evolutionary algorithm based on the snowdrift game to solve the MWVC problem. We use the evolutionary algorithm framework, and the snowdrift game is combined to construct and improve the initial solution. First, the network's vertex is regarded as an intelligent agent, and each vertex and its neighbors play a snowdrift game to form an initial solution. Then local search and global search are used to improve the initial solution. The solution is improved according to the proposed score function in the local search stage to obtain a better MWVC solution. The evolutionary algorithm is used in the global search stage to escape the local optimum. Experiments on different networks show that the proposed algorithm are effective on weighted networks. [ABSTRACT FROM AUTHOR]

In the multiway cut problem we are given a weighted undirected graph G = (V , E) and a set T ⊆ V of k terminals. The goal is to find a minimum weight set of edges E ′ ⊆ E with the property that by removing E ′ from G all the terminals become disconnected. In this paper we present a simple local search approximation algorithm for the multiway cut problem with approximation ratio 2 − 2 k . We present an experimental evaluation of the performance of our local search algorithm and show that it greatly outperforms the isolation heuristic of Dalhaus et al. and it has similar performance as the much more complex algorithms of Calinescu et al., Sharma and Vondrak, and Buchbinder et al. which have the currently best known approximation ratios for this problem. [ABSTRACT FROM AUTHOR]

The problem of k orthogonal line center is about computing a set of k axis-parallel lines for a given set of points in ℜ 2 such that the maximum among the distances between each point to its nearest line is minimized. A 2-factor approximation algorithm and a (5 3 , 3 2) bi-criteria approximation algorithm is presented for the problem. Both of them are deterministic approximation algorithms using combinatorial techniques and having sub-quadratic running times. [ABSTRACT FROM AUTHOR]

The identifying code problem for a given graph involves finding a minimum subset of vertices such that each vertex of the graph is uniquely specified by its nonempty neighborhood within the identifying code. The combinatorial optimization problem has a wide variety of applications in location and detection schemes. Finding an identifying code of minimum possible size is a difficult task. In fact, it has been proven to be computationally intractable (NP-complete). Therefore, the use of heuristics to provide good approximations in a reasonable amount of time is justified. In this work, we present a new population-based local search algorithm for finding identifying codes of minimum cost. Computational experiments show that the proposed approach was found to be more effective than other state-of-the-art algorithms at generating high-quality solutions in different types of graphs with varying numbers of vertices. [ABSTRACT FROM AUTHOR]