Search

Transportation networks frequently employ hub-and-spoke network architectures to route flows between many origin and destination pairs. Hub facilities work as switching points for flows in large networks. In this study, we focus on a problem, called the single allocation hub-and-spoke network design problem. In the problem, the goal is to allocate each non-hub node to exactly one of the given hub nodes so as to minimize the total transportation cost. The problem is essentially equivalent to another combinatorial optimization problem, called the metric labeling problem. The metric labeling problem was first introduced by Kleinberg and Tardos in 2002, motivated by application to segmentation problems in computer vision and related areas. In this study, we deal with a case where the set of hubs forms a star, which is encountered especially in telecommunication networks. We propose a polynomial-time randomized approximation algorithm for the problem, whose approximation ratio is less than 5.281. Our algorithms solve a linear relaxation problem and apply dependent rounding procedures. [ABSTRACT FROM AUTHOR]

We call a (not necessarily properly) edge-colored graph edge-color-avoiding connected if after the removal of edges of any single color, the graph remains connected. For vertex-colored graphs, similar definitions of color-avoiding connectivity can be given. In this article, we investigate the problem of determining the maximum number of edges that can be removed from either an edge- or a vertex-colored, color-avoiding connected graph so that it remains color-avoiding connected. First, we prove that this problem is NP-hard, and then, we give a polynomial-time approximation algorithm for it. To analyze the approximation factor of this algorithm, we determine the minimum number of edges of color-avoiding connected graphs on a given number of vertices and with a given number of colors. Furthermore, we also consider a generalization of edge-color-avoiding connectivity to matroids. [ABSTRACT FROM AUTHOR]

We improve the approximation ratio for Maximum Weight Series-Parallel Subgraph from 1 / 2 to 1 / 2 + 1 / 60. [ABSTRACT FROM AUTHOR]

In the network flow interdiction problem (NFI), an interdictor aims to remove arcs of total cost at most a given budget B from a network with given arc costs and capacities such that the value of a maximum flow from a source s to a sink t is minimized. We present a polynomial-time (B + 1) -approximation algorithm for NFI with unit arc costs, which is the first approximation algorithm for any variant of network flow interdiction whose approximation ratio only depends on the budget available to the interdictor, but not on the size of the network. [ABSTRACT FROM AUTHOR]

Continual Learning (CL) plays a crucial role in enhancing learning performance for both new and previous tasks in continuous data streams, thus contributing to the advancement of cognitive computing. However, CL faces a fundamental challenge known as the stability-plasticity quandary. In this research, we present an innovative and effective CL algorithm called Primary Null Space Projection (PNSP) to strike a balance between network plasticity and stability. PNSP consists of three main components. Firstly, it leverages the NSP-LRA algorithm to project the gradient of network parameters from previous tasks into a meticulously designed null space. NSP-LRA harnesses high-dimensional geometric information extracted from the feature covariance matrix through low-rank approximation algorithm to obtain the basis of null space dynamically. This process constructs an innovation null space and ensures the continuous updating of orthonormal bases to accommodate changes in the input data. Secondly, we propose a Consistency-guided Task-specific Feature Learning (CTFL) mechanism to tackle the issue of catastrophic forgetting and facilitate continual learning. CTFL achieves this by aligning feature vectors and maintaining consistent feature learning directions, thereby preventing the loss of previously acquired knowledge. Lastly, we introduce Label Guided Self-Distillation (LGSD), a technique that utilizes true labels to guide the distillation process and incorporates a dynamic temperature mechanism to enhance performance. To evaluate the effectiveness of our proposed method, we conduct experiments on the CIFAR100 and TinyImageNet datasets. The results demonstrate significant improvements over state-of-the-art methods. We have made the implementation code of our approach available for reference. • Proposal of PNSP method: Addresses stability-plasticity dilemma in continual learning. • NSP-LRA: Dynamically constructs null space for minimizing interference. • CTFL mechanism: Ensures consistent feature learning directions. • LGSD technique: Incorporates true labels and dynamic temperature for enhanced distillation. [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]

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]

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]

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]

We study the feedback vertex set problem in tournaments from the polyhedral point of view, and in particular we show that performing just one round of the Sherali–Adams hierarchy gives a relaxation with integrality gap 7 / 3. This allows us to derive a 7 / 3 -approximation algorithm for the feedback vertex set problem in tournaments that matches the best deterministic approximation guarantee due to Mnich, Williams, and Végh, and is a simplification and runtime improvement of their approach. [ABSTRACT FROM AUTHOR]

We introduce Tadam (Trust region ADAptive Moment estimation), a new optimizer based on the trust region of the second-order approximation of the loss using the Fisher information matrix. Despite the enhanced gradient estimations offered by second-order approximations, their practical implementation requires sizable batch sizes to estimate the second-order approximation matrices and perform matrix inversions. Consequently, integrating second-order approximations entails additional memory consumption and imposes substantial computational demands due to the inversion of large matrices. In light of these challenges, we have devised a second-order approximation algorithm that mitigates these issues by judiciously approximating the pertinent large matrix, requiring only a marginal increase in memory usage while minimizing the computational burden. Tadam approximates the loss up to the second order using the Fisher information matrix. Since estimating the Fisher information matrix is expensive in both memory and time, Tadam approximates the Fisher information matrix and reduces the computational burdens to the O (N) level. Furthermore, Tadam employs an adaptive trust region scheme to reduce approximate errors and guarantee stability. Tadam evaluates how well it minimizes the loss function and uses this information to adjust the trust region dynamically. In addition, Tadam adjusts the learning rate internally, even if we provide the learning rate as a fixed constant. We run several experiments to measure Tadam's performance against Adam, AMSGrad, Radam, and Nadam, which have the same space and time complexity as Tadam. The test results show that Tadam outperforms the benchmarks and finds reasonable solutions fast and stably. [ABSTRACT FROM AUTHOR]

The wind energy system's complicated characteristics have motivated many researchers to develop advanced and intelligent control strategies to ensure reliable and efficient system operation. Over the past few years, Artificial Neural Networks (ANN) have been widely employed in wind energy applications, and they are strongly recommended as a powerful and adequate tool for controlling wind turbine systems. The generator control block is a critical subsystem in the wind turbine chain, where a failed generator power control leads to an unstable operation process. The current work aims to verify the reliability of an ANN control of a DFIG integrated into a wind turbine system by considering the uncertainties in the machine parameters that affect the control's performance requirements. The major challenges encountered when applying reliability analyses are the system's high complexity and the expensive computational time required to achieve accurate results. In this context, the reliability assessment methodology adopted in this study combines Machine Learning techniques and advanced reliability approximation algorithms to optimize the computing time and ensure accurate results despite the system complexity. The obtained results demonstrate the reliability and effectiveness of ANN controllers in coping with machine parameter variations and maintaining the system at its optimal operating point. In addition, the results demonstrate the effectiveness of the reliability methodology implemented in this work by offering accurate approximations with a reasonable computing time. [ABSTRACT FROM AUTHOR]

We present BonnLogic , a timing optimization framework that replaces critical paths by logically equivalent realizations with less delay. Our tool allows to revise early decisions on the logical structure of the netlist in late physical design. The core routine of our framework is a new algorithm that constructs delay-optimized circuits for alternating And - Or paths with prescribed input arrival times. It is a sophisticated dynamic programming algorithm which is a common generalization of the previously best approaches. In contrast to all earlier methods, we avoid fixing the structure of sub-solutions before deciding on how to combine them, significantly expanding the search space of the algorithm. Our algorithm provably fulfills the best known approximation guarantees, almost always computes delay-optimum solutions, and empirically outperforms all previous approaches. In addition, we show how any algorithm for And - Or paths optimization which is restricted to integral arrival times can be generalized to fractional arrival times with the same guarantees on the delay. The reduction to And - Or path optimization allows us to optimize general combinatorial paths of arbitrary length in our logic restructuring framework BonnLogic. The framework is applied successfully as a late step in an industrial physical design flow. Experiments demonstrate the effectiveness of BonnLogic on industrial 7 nm instances. • We describe a new dynamic program for delay optimization of extended And - Or Paths. • We extend any And - Or paths optimization from integral to fractional arrival times. • On more than 95% of our test instances, our algorithm finds a delay-optimum circuit. • We propose BonnLogic , a framework for timing optimization of logic paths. • Experiments on recent 7nm chips show the effectiveness of BonnLogic. [ABSTRACT FROM AUTHOR]

• We introduce a new similarity measure for rooted, unordered, node-labeled trees. • We present an exact solver as well as a scalable 4-approximation algorithm. • We validate our approach using molecular trees and RNA secondary structures. Rooted trees are ubiquitous data structures which are used to model hierarchical objects from a plethora of different application domains. For various downstream analysis tasks, measures are needed that quantify (dis-)similarity between rooted trees. Many such measures exist, e. g., the widely used tree edit distance (TED). However, there are few algorithms to compute (dis-)similarity measures which are specifically designed for rooted, unordered, node-labeled trees and support input trees of different orders. To close this gap in the literature, we introduce the edge-preservation similarity (EPS). We show how to exactly compute EPS via integer quadratic programming on small instances and present a scalable 4-approximation algorithm. An evaluation on tree representations of pseudoknotted RNA secondary structures and acyclic molecular graphs shows that both exact and approximate (normalized) EPS better preserves functional similarities between the compared RNAs and molecules than the often-used TED. Python implementations of our algorithms and scripts to reproduce the results are available on GitHub: https://github.com/bionetslab/edge-preservation-similarity. [ABSTRACT FROM AUTHOR]

The maximization for the independence systems defined on graphs is a generalization of combinatorial optimization problems such as the maximum b -matching, the unweighted MAX-SAT, the matchoid, and the maximum timed matching problems. In this paper, we consider the problem under the local oracle model to investigate the global approximability of the problem by using the local approximability. We first analyze two simple algorithms FixedOrder and Greedy for the maximization under the model, which shows that they have no constant approximation ratio. Here algorithms FixedOrder and Greedy apply local oracles with fixed and greedy orders of vertices, respectively. We then propose two approximation algorithms for the k -degenerate graphs, whose approximation ratios are α + 2 k − 2 and α k , where α is the approximation ratio of local oracles. The second one can be generalized to the hypergraph setting. We also propose an (α + k) -approximation algorithm for bipartite graphs, in which the local independence systems in the one-side of vertices are k -systems with independence oracles. [ABSTRACT FROM AUTHOR]

Supersaturation of dissolved gas in water will cause fish to suffer from gas bubble diseases and even death. Therefore, it is imperative to illustrate the dissipation process of dissolved gas and then seek measures to remit the negative effects of dissolved gas supersaturation on fish. Generally, adding solid media (SM) to water has proven to be an effective and economical way to remove supersaturated dissolved gas from aquaculture water. While, the supersaturated dissolved gas dissipation framework in solid media containing water was still unclear. In this paper, combined with laboratory experiments and research available in the literature, the dissipation framework of dissolved gas was proposed along with the calculation of the liquid gas interfacial transfer mass, solid wall adsorption mass, porous media adsorption mass, and inner dissipation mass. The solid wall adsorption coefficient was found to follow a power function of the contact angle, and the porous adsorption coefficient logarithmically increased with the specific surface area. It was found that the inner dissipation coefficient exponentially increased with increasing total dissipation coefficient. Utilizing an approximation algorithm method, a model for the prediction of the dissipation coefficient was established. The research reported in this paper could contribute to enriching the research field of supersaturated dissolved dissipation and is significant for ecological and environmental protection. [Display omitted] [ABSTRACT FROM AUTHOR]

We present a new approximation algorithm for the minimum 2-edge-connected spanning subgraph problem. Its approximation ratio is 4 3 , which matches the current best ratio. The approximation ratio of the algorithm is 6 5 on subcubic graphs, which is an improvement upon the previous best ratio of 5 4. The algorithm is a novel extension of the primal-dual schema, which consists of two distinct phases. Both the algorithm and the analysis are much simpler than those of the previous approaches. [ABSTRACT FROM AUTHOR]

The squared metric k -facility location problem is a frequently encountered generalization of the k -means problem, where a specific cost should be paid for opening each facility. The current best approximation ratio for this problem is 44.473 + ϵ , which was obtained using a local search algorithm. We advance the state-of-the-art for the problem by devising a Lagrangian relaxation-based algorithm that achieves an improved approximation guarantee of 36.342 + ϵ. Our improvement comes from a new deterministic rounding approach, which exploits the properties of the squared metric. • We give a (36.342 + ϵ) -approximation algorithm for the squared metric k -facility location problem. • We obtain a well-behaved fractional solution to the squared metric k -facility location problem based on the framework of Lagrangian relaxation. • We give a new deterministic rounding approach that exploits the properties of the squared metric. [ABSTRACT FROM AUTHOR]

This work considers the Minimum Path-Collection Exact Cover (PCEC) and the Minimum k -Path Splitting Exact Cover (k-PSEC). Both problems receive a digraph G and a set P of paths in G , and their objective is to find a minimum cardinality set S of paths, whose elements are arc-disjoint and cover all arcs of G. Despite the similarities, the solutions for each problem must satisfy different properties. For k-PSEC , the set S must be obtained by splitting the paths in P in order to guarantee that no element of S has length greater than a given integer k. For PCEC , the paths in P cannot be split, and the elements of S are single arcs of G or complete paths of P. PCEC and k-PSEC have practical applications in network design and network monitoring systems, being also natural versions of graph covering problems. However, there are no theoretical studies on their complexity. This work not only presents NP-hardness results for the problems, but also proves that, unless P = NP , PCEC cannot be | P | O (1) -approximated in polynomial-time. Moreover, polynomial-time algorithms are presented for paths, cycles, and trees, and polynomial-time approximation algorithms are proposed for special cases of k-PSEC. [ABSTRACT FROM AUTHOR]

Abstract polymer models are systems of weighted objects, called polymers, equipped with an incompatibility relation. An important quantity associated with such models is the partition function, which is the weighted sum over all sets of compatible polymers. Various approximation problems reduce to approximating the partition function of a polymer model. Central to the existence of such approximation algorithms are weight conditions of the respective polymer model. Such conditions are derived either via complex analysis or via probabilistic arguments. We follow the latter path and establish a new condition—the clique dynamics condition—, which is less restrictive than the ones in the literature. We introduce a new Markov chain where the clique dynamics condition implies rapid mixing by utilizing cliques of incompatible polymers that naturally arise from the translation of algorithmic problems into polymer models. This leads to improved parameter ranges for several approximation algorithms, such as a factor of at least 2 1 / α for the hard-core model on bipartite α -expanders. [ABSTRACT FROM AUTHOR]

The traveling salesman problem (TSP) is one of the classic research topics in the field of operations research, graph theory and computer science. In this paper, we propose a generalized model of traveling salesman problem, denoted by generalized traveling salesman path problem. Let G = (V , E , c) be a weighted complete graph, in which c is a nonnegative metric cost function on edge set E , i.e., c : E → R +. The traveling salesman path problem aims to find a Hamiltonian path in G with minimum cost. Compared to the traveling salesman path problem, we are given extra vertex subset V ′ and edge subset E ′ in the problem proposed in this paper; its goal is to construct a path which traverses all the edges in E ′ while only needs to visit each vertex in V ′ exactly once. Based on integer programming, we give a mathematical model of the problem, and design a 1 + 5 2 -approximation algorithm for the problem by combining linear programming rounding strategy and a special graph structure. • In this paper, we consider a generalized model of traveling salesman problem. • Based on integer programming, we give a mathematical model of the problem. • Combining linear programming rounding strategy and a special graph structure, we propose a 1 + 5 2 -approximation algorithm. [ABSTRACT FROM AUTHOR]

We investigate two parallel dedicated machine scheduling with conflict constraints. The problem of minimizing the makespan has been shown to be NP-hard in the strong sense under the assumption that the processing sequence of jobs on one machine is given and fixed a priori. The problem without any fixed sequence was previously recognized as weakly NP-hard. In this paper, we first present a 9 5 -approximation algorithm for the problem with a fixed sequence. Then we show that the tight approximation ratios of the algorithm are 7 4 and 5 3 for two subproblems which remain strongly NP-hard. We also send an improved algorithm with approximation ratio 3 − 2 ≈ 1.586 for one subproblem. Finally, we prove that the problem without any fixed sequence is actually strongly NP-hard, and design a 5 3 -approximation algorithm. • Consider the problem of scheduling with conflict constraints on two parallel dedicated machines. • Present a 9 5 -approximation algorithm for the strongly NP-hard case where jobs on one machine have a fixed processing sequence, and give improvements to its hard subproblems. • Prove that the problem without any fixed sequence is strongly NP-hard too and propose a 5 3 -approximation algorithm. [ABSTRACT FROM AUTHOR]

Emerging wireless and mobile applications, such as border intrusion detection with station-based drones, brought a new barrier coverage problem of using sink-based mobile sensors to cover a given line barrier with minimum energy consumption. In this paper, we focus on the uniform sink-based line barrier coverage (SLBC) problem, in which we are given a line barrier and k sink stations distributed on the plane which can emit an infinite number of sensors with an identical sensing radius. The problem aims to find their final positions on the barrier for the sensors emitted by the stations, such that the total moving distance of the sensors is minimized and each point of the barrier is within the sensing area of at least one sensor. We first observe the geometric structure of an optimal solution that any optimal solution can be considered as a set of intersecting tangent (disk) segments, where a tangent (disk) segment is a sequence of tangent disks. Then, we devise an algorithm to calculate all possible tangent (disk) segments and another algorithm to calculate the near-optimal positions for each of such segments. After computing all tangent (disk) segments and their near-optimal positions, an algorithm is proposed to transform uniform SLBC into an instance of the shortest path problem. It is shown the whole algorithm deserves a runtime O (k 2 log ⁡ k r ε) and consumes at most ε more movement than an optimal solution, where ε is any given positive real number, and r and k are the sensor radius and the number of sink stations, respectively. • The algorithm consumes a runtime O (k 2 log ⁡ k r ε) and produces a solution with at most ε more movement than that of an optimum solution. • With the runtime and the performance guarantee, the proposed algorithm behaves in a manner similar to a polynomial-time exact algorithm. • We proved several geometric properties of an optimum solution, which might have possible applications in other variants of the problem. [ABSTRACT FROM AUTHOR]

The rooted Budgeted Cycle Cover (BCC) problem is a fundamental optimization problem arising in wireless sensor networks and vehicle routing. Given a metric space (V , w) with vertex set V consisting of two parts D (containing depots) and V ∖ D (containing nodes), and a budget B ≥ 0 , the rooted BCC problem asks to find a minimum number of cycles to cover all the nodes in V ∖ D , satisfying that each cycle has length at most B and each cycle must contain a depot in D. In this paper, we give new approximation algorithms for the rooted BCC problem. For the rooted BCC problem with single depot, we give an O (log ⁡ B μ) -approximation algorithm, where μ is the minimum difference of any two different distances between the vertices in V and the root. For the rooted BCC problem with multiple depots, we give an O (log ⁡ n) -approximation algorithm, where n is the number of vertices. We also test our algorithms on the randomly generated instances. The experimental results show that the algorithms have good performance in practice. • A log-factor approximation algorithm for the single depot budgeted cycle cover problem. • A log-factor approximation algorithm for the multi-depot budgeted cycle cover problem. • Experiments on randomly generated instances show good performance of the algorithms. [ABSTRACT FROM AUTHOR]

In this work, we study a range of constrained versions of the k-supplier and k-center problems. In the classical (unconstrained) k -supplier problem, we are given a set of clients C in a metric space X , with distance function d (. ,.). We are also given a set of feasible facility locations L ⊆ X. The goal is to open a set F of k facilities in L to minimize the maximum distance of any client to the closest open facility, i.e., minimize, cost (F , C) ≡ max j ∈ C ⁡ { d (F , j) } , where d (F , j) is the distance of client j to the closest facility in F. The k -center problem is a special case of the k -supplier problem where L = C. We study various constrained versions of the k -supplier problem such as: capacitated , fault-tolerant , ℓ -diversity, etc. These problems fall under a broad framework of constrained clustering. A unified framework for constrained clustering was proposed by Ding and Xu [Algorithmica 2020] in the context of the k -median and k -means objectives. We extend this framework to the k -supplier and k -center objectives in this work. This unified framework allows us to obtain results simultaneously for the following constrained versions of the k -supplier problem: r-gather, r-capacity, balanced, chromatic, fault-tolerant, strongly private, ℓ-diversity, and fair k-supplier problems, with and without outliers. We design Fixed-Parameter Tractable (FPT) algorithms for these problems. FPT algorithms have polynomial running time if the parameter under consideration is a constant. This may be relevant even to a practitioner since the parameter k is a small number in many real clustering scenarios. We obtain the following results: • We give 3 and 2 approximation algorithms for the constrained k -supplier and k -center problems, respectively, with FPT running time k O (k) ⋅ n O (1) , where n = | C ∪ L |. Moreover, these approximation guarantees are tight; that is, for any constant ε > 0 , no algorithm can achieve (3 − ε) and (2 − ε) approximation guarantees for the constrained k -supplier and k -center problems in FPT time, assuming FPT ≠ W [ 2 ]. • We study the constrained clustering problem with outliers. Our algorithm gives 3 and 2 approximation guarantees for the constrained outlier k -supplier and k -center problems, respectively, with FPT running time (k + m) O (k) ⋅ n O (1) , where n = | C ∪ L | and m is the number of outliers. • Our techniques generalise for distance function d (. ,.) z. That is, for any positive real number z , if the cost of a client is defined by d (. ,.) z instead of d (. ,.) , then our algorithm gives 3 z and 2 z approximation guarantees for the constrained k -supplier and k -center problems, respectively. • We design 3 approximation algorithm for a wide range of constrained k -supplier problems with FPT running time f (k). p o l y (n). • We design 2 approximation algorithm for a range of constrained k -center problems with FPT running time f (k). p o l y (n). • We extend the algorithm to outlier setting with FPT running time f (k , m). p o l y (n) , where m = number of outliers. • We show matching lower bounds for the constrained k -supplier and k -center problems in the outlier and non-outlier settings. [ABSTRACT FROM AUTHOR]

We study worst-case fairness in resource allocation and cooperative games with transferable utility, the stable division most dissimilar to a normative standard of fairness. Motivated by welfare economics, similarity is quantified using information-theoretic divergences. Worst-case fairness aims to parallel the spirit of the price of anarchy from noncooperative game theory, quantifying how much unfairness is compatible with coalitional rationality. Computing worst-case fairness is tractable in weighted voting games and classes of coalitional skill games, but NP-hard in highway allocation, induced-subgraph games and some task-count coalitional skill games. In these cases we show approximation algorithms that yield constant approximations. We also upper bound the performance of a Reverse Greedy algorithm on general convex games in terms of two game-specific constants. • We study worst-case fairness in resource allocation and cooperative games with transferable utility. • We consider the imputation in the core with the largest divergence with a fixed imputation, a "standard of fairness". • We study the problem for several classes of cooperative games with transferable utility. • In cases when worst-case fairness is intractable we give algorithms that produce an approximately worst-case fair imputation. [ABSTRACT FROM AUTHOR]

A mixed dominating set of a graph G = (V , E) is a mixed set D of vertices and edges, such that for every edge or vertex, if it is not in D , then it is adjacent or incident to at least one vertex or edge in D. The mixed domination problem is to find a mixed dominating set with a minimum cardinality. It has applications in system control and some other scenarios and it is NP -hard to compute an optimal solution. This paper studies approximation algorithms and hardness of the weighted mixed dominating set problem. The weighted version is a generalization of the unweighted version, where all vertices are assigned the same nonnegative weight w v and all edges are assigned the same nonnegative weight w e , and the question is to find a mixed dominating set with a minimum total weight. Although the mixed dominating set problem has a simple 2-approximation algorithm, few approximation results for the weighted version are known. The main contributions of this paper include: 1. for w e ≥ w v , a 2-approximation algorithm; 2. for w e ≥ 2 w v , inapproximability within ratio 1.3606 unless P = N P and within ratio 2 under UGC; 3. for 2 w v > w e ≥ w v , inapproximability within ratio 1.1803 unless P = N P and within ratio 1.5 under UGC; 4. for w e < w v , inapproximability within ratio (1 − ϵ) ln ⁡ | V | unless P = N P for any ϵ > 0. [ABSTRACT FROM AUTHOR]

Active Queue Management (AQM) for mitigating Internet congestion has been addressed via various feedback control syntheses, especially P, PI, and PID regulators, by using a linear approximation where the "round trip time," i.e., the delay, is assumed to be constant. This constraint is lifted here by using a nonlinear modeling with a variable delay, introduced more than 20 years ago. This delay, intimately linked to the congestion phenomenon, may be viewed as " a flat output." All other system variables, especially the control variable, i.e., the packet loss ratio, are expressed as a function of the delay and its derivatives: they are frozen if the delay is kept constant. This flatness-like property, which demonstrates the mathematical discrepancy of the linear approximation adopted until today, yields also our control strategy in two steps: Firstly, designing an open-loop control, thanks to straightforward Flatness-Based Control (FBC) techniques, and secondly, closing the loop via Model-Free Control (MFC) in order to take into account severe model mismatches, like, here, the number of TCP sessions. Several convincing computer simulations, which are easily implementable, are presented and discussed. • Perhaps the first work using a nonlinear differential equation with a variable delay. • A new flatness-like property is encountered: the delay is a flat output. • Flatness and model-free control lead to easily implementable feedback laws. • Computer experiments show great robustness w.r.t. severe TCP connections variations. • Usual constant linear delay approximations contradict the AQM nonlinear modeling. [ABSTRACT FROM AUTHOR]

Broadcasting in a computer network is a method of transferring a message to all recipients simultaneously. It is common in this situation to use a tree with many leaves to perform the broadcast, as internal nodes have to forward the messages received, while leaves are only receptors. We consider the subjacent problem of, given a directed graph D , finding a spanning arborescence of D , if one exists, with the maximum number of leaves. In this paper, we concentrate on the class of rooted directed acyclic graphs, for which the problem is known to be MaxSNP-hard. A 2-approximation was previously known for this problem on this class of directed graphs. We improve on this result, presenting a 3 2 -approximation. We also adapt a result for the undirected case and derive an inapproximability result for the vertex-weighted version of Maximum Leaf Spanning Arborescence on rooted directed acyclic graphs. [ABSTRACT FROM AUTHOR]

In this work we investigate the problem of estimating the percolation centrality of all vertices in a weighted graph. The percolation centrality measure quantifies the importance of a vertex in a graph that is going through a contagious process. The fastest exact algorithm for the computation of this measure in a graph G with n vertices and m edges runs in O (n 3). Let Diam V (G) be the maximum number of vertices in a shortest path in G. In this paper we present an expected O (m log n log Diam V (G)) time approximation algorithm for the estimation of the percolation centrality for all vertices of G. We show in our experimental analysis that in the case of real-world complex networks, the output produced by our algorithm returns approximations that are even closer to the exact values than its guarantee in terms of theoretical worst case analysis. [ABSTRACT FROM AUTHOR]

We consider the line planning problem in public transport in the Parametric City, an idealized model that captures typical scenarios by a (small) number of parameters. The Parametric City is rotation symmetric, but optimal line plans are not always symmetric. This raises the question to quantify the symmetry gap between the best symmetric and the overall best solution. For our analysis, we formulate the line planning problem as a mixed integer linear program, that can be solved in polynomial time if the solutions are forced to be symmetric. We prove that the symmetry gap is small when a specific Parametric City parameter is fixed, and we give an approximation algorithm for line planning in the Parametric City in this case. While the symmetry gap can be arbitrarily large in general, we show that symmetric line plans are a good choice in most practical situations. • Optimal line plans in an entirely symmetric city model are not symmetric by default. • Line planning on an idealized infrastructure model to represent generic cities. • Analytical examination of the deviation from the optimum by symmetry assumption. • While infinitely large in practice, the symmetry gap is provably small in practice. • Development of an approximation algorithm utilizing the symmetric structure. [ABSTRACT FROM AUTHOR]

Although the knapsack-constrained and k -system-constrained non-monotone adaptive submodular maximization have been well studied in the literature, it has only been settled given the additional assumption of pointwise submodularity. In this paper, we remove the common assumption on pointwise submodularity and propose the first approximation solutions for both knapsack and k -system constrained adaptive submodular maximization problems. Inspired by two recent studies on non-monotone adaptive submodular maximization, we develop a sampling-based randomized algorithm that achieves a 1 10 approximation ratio for the case of a knapsack constraint and that achieves a 1 2 k + 4 approximation ratio for the case of a k -system constraint. • We study the non-monotone adaptive submodular maximization problem. • We present a 1 10 approximation algorithm for knapsack constraints. • We present a 1 2 k + 4 approximation algorithm for k -system constraints. • Our results do not rely on pointwise submodularity. [ABSTRACT FROM AUTHOR]

Consistent query answering (CQA) is a widely accepted paradigm for querying inconsistent knowledge bases (KBs). A consistent answer to a query is a tuple that is an answer to the query over every repair of the KB, which is in turn a consistent KB whose extensional knowledge "minimally" differs from the original one's. This coarse-grained classification of answers into consistent and non-consistent ones lacks any information about their degree of consistency, i.e., how likely it is that a tuple is an answer to the query, when considering all the repaired KBs. To overcome this limitation, we consider a fine-grained notion of repair for KBs with equality-generating dependencies (EGDs), based on attribute-level updates, and exploit this notion to propose a probabilistic CQA approach, which associates a confidence to each answer, thereby providing more informative query answers. We first show that computing the query answer confidence is # P -hard. Then, in the light of this intractability result, we study the existence of efficient randomized, approximation schemes. In particular, we show that absolute error approximation schemes always exist in the general case, while more refined relative error approximation schemes, i.e., fully polynomial-time, randomized approximation schemes (FPRAS) exist when assuming that the constraints of the knowledge base are primary keys. Finally, we extend our framework to knowledge bases with tuple-generating dependencies (TGDs) and generalize our approximability results to the new setting, and prove additional inapproximability results. [ABSTRACT FROM AUTHOR]

Given a complete undirected graph G = (V , E) , where V is the vertex set partitioned into K clusters V 1 , V 2 , ... , V K and E is the edge set with edge weights satisfying triangle inequality, and a positive integer k , the min-max clustered k-traveling salesmen problem (min-max C k -TSP) asks to find a set of k tours to visit all vertices, such that each cluster is visited by exactly one tour and the vertices of each cluster are visited consecutively. The objective is to minimize the weight of the maximum weight tour. The problem is known to be NP-hard even when k = 1 and K = 1. In this paper, we consider two variants of the problem. The first one is all the k tours have a common predefined starting vertex, and the other one is no starting vertex of any tour is specified. For both the variants we propose the first constant-factor approximation algorithms with ratios 5.5 and 16, respectively. • We consider the min-max clustered k-traveling salesmen problem. • We propose a 5.5-approximation algorithm for the case in which all the k tours have a common predefined starting vertex. • We provide a 16-approximation algorithm for the case in which no starting vertex of any tour is specified. • Both algorithms are the first constant-factor approximation algorithms. [ABSTRACT FROM AUTHOR]

• We study the heterogeneous weighted delivery (HWD) problem, which was introduced in [Bärtschi et al., STACS'17]. • We efficiently 8-approximate HWD with k = O (log ⁡ n) agents, closing an open problem in [Bärtschi et al., ATMOS'17]. • We design a O (k) -approximation algorithm that runs in polynomial time regardless of the value of k. • We design a polynomial-time O ˜ (log 3 ⁡ n) -approximation algorithm. • We show that the HWD problem is 36-approximable in polynomial time when each agent has one of two possible consumption rates. We study the heterogeneous weighted delivery (HWD) problem introduced in [Bärtschi et al., STACS'17] where k heterogeneous mobile agents (e.g., robots, vehicles, etc.), initially positioned on vertices of an n -vertex edge-weighted graph G , have to deliver m messages. Each message is initially placed on a source vertex of G and needs to be delivered to a target vertex of G. Each agent can move along the edges of G and carry at most one message at any time. Each agent has a rate of energy consumption per unit of traveled distance and the goal is that of delivering all messages using the minimum overall amount of energy. This problem has been shown to be NP-hard even when k = 1 , and is 4 ρ -approximable where ρ is the ratio between the maximum and minimum energy consumption of the agents. In this paper, we provide approximation algorithms with approximation ratios independent of the energy consumption rates. First, we design a polynomial-time 8-approximation algorithm for k = O (log ⁡ n) , closing a problem left open in [Bärtschi et al., ATMOS'17]. This algorithm can be turned into an O (k) -approximation algorithm that always runs in polynomial-time, regardless of the values of k. Then, we show that HWD problem is 36-approximable in polynomial-time when each agent has one of two possible consumption rates. Finally, we design a polynomial-time O ˜ (log 3 ⁡ n) -approximation algorithm for the general case. [ABSTRACT FROM AUTHOR]

Consider an information diffusion process on a graph G that starts with k > 0 burnt vertices, and at each subsequent step, burns the neighbors of the currently burnt vertices, as well as k other unburnt vertices. The k-burning number of G is the minimum number of steps b k (G) such that all the vertices can be burned within b k (G) steps. Note that the last step may have smaller than k unburnt vertices available, where all of them are burned. The 1-burning number coincides with the well-known burning number problem, which was proposed to model the spread of social contagion. The generalization to k -burning number allows us to examine different worst-case contagion scenarios by varying the spread factor k. In this paper we prove that computing k -burning number is APX-hard, for any fixed constant k. We then give an O ((n + m) log ⁡ n) -time 3-approximation algorithm for computing k -burning number, for any k ≥ 1 , where n and m are the number of vertices and edges, respectively. Finally, we show that even if the burning sources are given as an input, computing a burning sequence itself is an NP-hard problem. [ABSTRACT FROM AUTHOR]

In the capacitated facility location problem, we are given a set F of potential facilities and a set D of clients, where each facility has a capacity and an open cost, and each client has a demand to be served by the facilities with service costs. The goal is to open some facilities in F and assign all clients in D to these open facilities such that the total cost is minimum. Based on the natural integer programming formulation, Levi et al. [8] presented an LP-based 5-approximation algorithm for this problem under the assumption that the facility costs are uniform. Based on the same integer programming formulation, we remove the uniformity assumption and present an (R + R 2 + 8 R 2 + 3) -approximation algorithm for the capacitated facility location problem, where R is the upper bound of the ratio between facility costs. Our result is a slight extension of the corresponding result in [8] , as when R = 1 the worst-case ratio of our algorithm is R + R 2 + 8 R 2 + 3 = 5. [ABSTRACT FROM AUTHOR]

In a minimum general partial dominating set problem (MinGPDS), given a graph G = (V , E) , a profit function p : V → R + and a threshold K , the goal is to find a minimum subset of vertices D ⊆ V such that the total profit of those vertices dominated by D is at least K (a vertex is dominated by D if it is either in D or has at least one neighbor in D). In a maximum general budgeted dominating set problem (MaxGBDS), given a budget B , the goal is to find a vertex set D with at most B vertices such that the total profit of those vertices dominated by D is as large as possible. We present the first parallel algorithms for MinGPDS and MaxGBDS in unit disk graphs. They both run in O (log ⁡ n) rounds on O (n) machines, and achieve constant approximation ratios. • First parallel algorithms for minimum partial dominating set and maximum budgeted dominating set in unit disk graphs. • Constant approximation ratios are obtained in logarithmic rounds. • Overcome the challenge brought by the ̀̀partial" consideration by implementing a greedy idea in a parallelized manner. [ABSTRACT FROM AUTHOR]

Let G (V , E , c , w) be a weighted graph with vertex set V , edge set E , vertex-capacity function c : V → R + , and edge-weight function w : E → R + . In Bumblebee visitation problem , a mobile agent Bumblebee, denoted by B , begins by entering a vertex of the graph, and then moves along the edges of the graph. When B moves along an edge e = u v , both c (u) and c (v) are decreased by w (e). The Bumblebee visitation problem deals with placing and moving B in G such that the sum of the residual-capacities at the visited vertices is maximum. We consider four variants of this problem depending on edge-weights and constraints on the possible movements of B. The four variants are uniform-weight-constrained Bumblebee Visitation problem , variable-weight-constrained Bumblebee Visitation problem , uniform-weight-unconstrained Bumblebee Visitation problem , and variable-weight-unconstrained Bumblebee Visitation problem. We show that all four variants are NP-hard for general graphs, and the variable-weight constrained variant is NP-hard even for star graphs (K 1 , n). On the positive side, for the uniform-weight constrained variant, we give a dynamic programming based linear-time algorithm for trees and a quadratic-time algorithm for cactus. We then extend these algorithms for the variable-weight unconstrained variant. We also give a 3-factor approximation algorithm for the uniform-weight unconstrained variant where each vertex-capacity is at least five. [ABSTRACT FROM AUTHOR]

In this work we introduce the Minimum Rural Postmen Cover Problem (MRPCP) and the Minimum Chinese Postmen Cover Problem (MCPCP). The MRPCP aims to cover a given subset R of edges of an undirected weighted graph G = (V , E) by a minimum size set of closed walks of bounded length λ. The MCPCP is a special case of the MRPCP with R = E. We give the first approximation algorithms for these two problems, which have constant approximation ratios of 5 and 4, respectively. [ABSTRACT FROM AUTHOR]

Temporal graphs are graphs where the topology and/or other properties of the graph change with time. They have been used to model applications with temporal information in various domains. Problems on static graphs become more challenging to solve in temporal graphs because of dynamically changing topology, and many recent works have explored graph problems on temporal graphs. In this paper, we define a type of matching called 0-1 timed matching for temporal graphs, and investigate the problem of finding a maximum 0-1 timed matching for different classes of temporal graphs. We assume that only the edge set of the temporal graph changes with time. Thus, a temporal graph can be represented by associating each edge with one or more non-overlapping discrete time intervals for which that edge exists. We first prove that the problem is NP-complete for rooted temporal trees when each edge is associated with two or more time intervals. We then propose an O (n log n) time algorithm for the problem on a rooted temporal tree with n vertices when each edge is associated with exactly one time interval. The problem is then shown to be NP-complete also for bipartite temporal graphs even when each edge is associated with a single time interval and degree of each vertex is bounded by a constant k ≥ 3. We next investigate approximation algorithms for the problem for temporal graphs where each edge is associated with more than one time intervals. It is first shown that there is no 1 n 1 − ϵ -factor approximation algorithm for the problem for any ϵ > 0 even on a rooted temporal tree with n vertices unless NP = ZPP. We then present a 5 2 N ∗ + 3 -factor approximation algorithm for the problem for general temporal graphs where N ∗ is the average number of edges overlapping in time with each edge in the temporal graph. The same algorithm is also a constant-factor approximation algorithm for temporal graphs with degree of each vertex bounded by a constant. [ABSTRACT FROM AUTHOR]

The anti-Ramsey number , a r (G , H) is the minimum integer k such that in any edge colouring of G with k colours there is a rainbow subgraph isomorphic to H , namely, a copy of H with each of its edges assigned a different colour. The notion was introduced by Erdös and Simonovits in 1973. Since then the parameter has been studied extensively. The case when H is a star graph was considered by several graph theorists from the combinatorial point of view. Recently this case received the attention of researchers from the algorithm community because of its applications in interface modelling of wireless networks. To the algorithm community, the problem is known as maximum edge q -colouring problem: Find a colouring of the edges of G , maximizing the number of colours satisfying the constraint that each vertex spans at most q colours on its incident edges. It is easy to see that the maximum value of the above optimization problem equals a r (G , K 1 , q + 1) − 1. In this paper, we study the maximum edge 2-colouring problem from the approximation algorithm point of view. The case q = 2 is particularly interesting due to its application in real-life problems. Algorithmically, this problem is known to be NP-hard for q ≥ 2. For the case of q = 2 , it is also known that no polynomial-time algorithm can approximate to a factor less than 3 / 2 assuming the unique games conjecture. Feng et al. showed a 2-approximation algorithm for this problem. Later Adamaszek and Popa presented a 5 / 3 -approximation algorithm with the additional assumption that the input graph has a perfect matching. Note that the obvious but the only known algorithm issues different colours to the edges of a maximum matching (say M) and different colours to the connected components of G ∖ M. In this article, we give a new analysis of the aforementioned algorithm to show that for triangle-free graphs with perfect matching the approximation ratio is 8 / 5. We also show that this algorithm cannot achieve a factor better than 58 / 37 on triangle free graphs that has a perfect matching. The contribution of the paper is a completely new, deeper and closer analysis of how the optimum achieves a higher number of colours than the matching based algorithm, mentioned above. [ABSTRACT FROM AUTHOR]

We characterize the optimal solution to the linear programming relaxation of the standard formulation for the minimum satisfiability problem. We give a O (n m 2) combinatorial algorithm to solve the fractional version of the minimum satisfiability problem optimally where n (m) is the number of variables (clauses). As a by-product, we obtain a 2 (1 − 1 / 2 k) approximation algorithm for the minimum satisfiability problem where k is the maximum number of literals in any clause. [ABSTRACT FROM AUTHOR]