Search

• 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 research, we investigate Hilfer-type FDDEs of both linear and nonlinear nature, with orders α and β. We studied some Riemann-Liouville, Caputo-Liouville, and Hilfer fractional derivatives properties; and then used them to convert our fractional delay problem into an equivalent fractional Volterra delay problem. After that, for the resulting fractional Volterra delay problem, using the CMT, existence-uniqueness is demonstrated. For numerical solutions, we studied the orthogonal shifted Legendre polynomials and used them as the basis for the Galerkin algorithm to find an approximation solution to the corresponding FDDE. By employing this algorithm, the provided FDDE is converted into a series of algebraic systems. By solving this system, the approximated solutions for the equation are obtained. The main algorithm advantage is that the number of needed iterations is low compared with the soft gained results. Some linear and nonlinear numerical applications together with several figures and tables are utilized to prove the performance and accuracy of the algorithm. The outcomes results are considered according to the given analysis and the numerical method was offered in the last section with several hints to guide future work. [ABSTRACT FROM AUTHOR]

Subgraph Problems are optimization problems on graphs where a solution is a subgraph that satisfies some property and optimizes some measure. Examples include shortest path, minimum cut, maximum matching, or vertex cover. In reality, however, one often deals with time-dependent data, i.e., the input graph may change over time and we need to adapt our solution accordingly. We are interested in guaranteeing optimal solutions after each graph change while retaining as much of the previous solution as possible. Even if the subgraph problem itself is polynomial-time computable, this multistage variant turns out to be NP-hard in most cases. We present an algorithmic framework that—for any subgraph problem of a certain type—guarantees an optimal solution for each point in time and provides an approximation guarantee for the similarity between subsequent solutions. We show that the class of applicable multistage subgraph problems is very rich and that proving membership to this class is mostly straightforward. As examples, we explicitly state these proofs and obtain corresponding approximation algorithms for the natural multistage versions of Shortest s-t- Path, Perfect Matching, Minimum s-t -Cut—and further classical problems on bipartite or planar graphs, namely Maximum Cut, Vertex Cover, and Independent Set. We also report that all these problems are already NP-hard on only two stages. [ABSTRACT FROM AUTHOR]

We consider a number of min-max coverage problems. In each problem, the input is an unweighted graph G and an integer k, and possibly some additional information, such as a root vertex r. In the Min-Max Path Cover problem, the task is to cover all vertices of the graph by k walks, minimizing the length of the longest walk. The variant of Min-Max Path Cover in which all walks start and end at the same prescribed root vertex r is called the k-Traveling Salesmen Problem. In the Min-Max Tree Cover problem, the task is to cover all vertices of the graph by k trees, minimizing the size (number of edges) of the largest tree. In the rooted version, Min-Max k-Rooted Tree Cover, the input also contains k roots r 1 ,..., r k , and the i th tree must contain the root r i. These four problems are all known to be APX-hard and to admit a constant-factor approximation. In this paper, we initiate the systematic study of these problems on trees and, more generally, on graphs of constant treewidth. As opposed to most graph problems, all four of the above coverage problems remain NP-hard even when G is a tree. We obtain an nO(k)-time exact algorithm for all four problems on graphs of bounded treewidth. Our main contribution is a quasi-polynomial-time approximation scheme (QPTAS) for the k-Traveling Salesmen Problem, Min-Max Path Cover, and Min-Max Tree Cover on graphs of bounded treewidth. [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]

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]

Active Disturbance Rejection Control (ADRC) emerges as a promising control method that can effectively handle uncertainties and disturbances. However, many model-based ADRC tuning methods turn laborious to achieve satisfactory control performance, when the critical process parameters are difficult to accurately obtain, especially the time delay information. To this end, this paper aims to propose a data-driven iterative tuning method for time-delayed ADRC (TD-ADRC). Based on parameter scaling technique, the quantitative correlation among control performance, robustness and normalized controller parameters are investigated. It is then used to design robust nominal controller. Then, based on the TD-ADRC inner-loop equivalent structure, an iterative feedback tuning (IFT) method is proposed to optimally obtain the nominal first order plus time delay (FOPTD) process model. Its unbiasedness and convergence are also described. With the empirical relations and the IFT stochastic approximation algorithm, a data-driven iterative tuning method for TA-ADRC is proposed, which allows a reasonable trade-off between system performance and robustness. Simulation results validate the efficacy of the proposed method, and a water-tank control experiment depicts a promising prospect in control practice. • A data-driven iterative tuning method for time-delayed ADRC is proposed considering both control performance and robustness. • An unbiased gradient estimate with respect to the model parameters under noise conditions is derived. • Control parameters are tuned iteratively through a data-driven method: iterative feedback tuning method. [ABSTRACT FROM AUTHOR]

• A novel two-stage coordinated risk-averse distributionally robust optimization model for maintenance and generation schedules of wind turbines is proposed. • A risk-averse measurement method is combined with DRO model for considering the operation risks. • A feasible route generating algorithm for reducing the number of required binary variables is proposed. • The transformation of proposed model and the specific algorithm is proposed to solve the proposed model. • Test results show the computational accuracy and efficiency of the proposed method. The coordinated optimization of maintenance and generation schedules of multiple offshore wind farms (OWFs) bring great benefits in reducing the maintenance and operation cost of OWF cluster. Firstly, a two-stage coordinated risk-averse distributionally robust optimization (CRDRO) model for maintenance and generation schedules of wind turbines (WTs) in OWF cluster is proposed. This model takes into account uncertainties related to the prediction errors in WTs' maximum available active power outputs, the travel time of maintenance vessels, and the high operational cost risks associated with these uncertainties. A feasible route generating algorithm is designed to obtain all feasible maintenance combinations for WTs and the corresponding routes of maintenance vessels for the CRDRO model. The risk-averse term, which is a weighted sum of expected operation costs and GlueVaR value, is used to measure the tail risk of the worst probability distribution. To solve the two-stage CRDRO model, the risk-averse term is simplified into the form of expected value calculation, which can be further transformed into the tractable form by using the strong duality theorem. Finally, the two-stage CRDRO model is solved by the column-and-constraint generation algorithm, with the nonconvex sub-problem being addressed by the outer approximation algorithm. Case studies on an real-world cluster comprising three OWFs verify the correctness and efficiency of the proposed method, and demonstrate that the CRDRO model enhances the overall economic efficiency and reduces the high operational cost risk under extreme scenarios. [ABSTRACT FROM AUTHOR]

Machine learning-based model predictive control (ML-MPC) has been developed to control nonlinear processes with unknown first-principles models. While ML models can capture nonlinear dynamics of complex systems, the complexity of ML models leads to increased computation time for real-time implementation of ML-MPC. To address this issue, in this work, we propose an explicit ML-MPC framework for nonlinear processes using multi-parametric programming. Specifically, a self-adaptive approximation algorithm is first developed to obtain a piecewise linear affine function that approximates the behaviors of ML models. Then, multi-parametric quadratic programming (mpQP) problems are formulated to generate the solution map for states in discretized state–space. Furthermore, to accelerate the implementation of explicit ML-MPC, a neighbor-first search algorithm is developed. Finally, an example of a chemical reactor is used to demonstrate the effectiveness of the explicit ML-MPC. • An explicit MPC framework for MPCs using a general class of ML models. • A self-adaptive algorithm for approximating ML models with the desired accuracy. • Neighbor-first search algorithm for accelerating implementation of explicit ML-MPC. • Improvement of computational efficiency demonstrated in a chemical process example. [ABSTRACT FROM AUTHOR]

In this paper, we propose a graph classification approach for automatically determining whether to use a monolithic or a decomposition-based solution method. In this approach, an optimization problem is represented as a graph that captures the structural and functional coupling among the variables and constraints of the problem via an appropriate set of features. Given this representation, a graph classifier can be built to assist a solver in selecting the best solution strategy for a given problem with respect to some metric of choice. The proposed approach is used to develop a classifier that determines whether a convex Mixed Integer Nonlinear Programming problem should be solved using branch and bound or the outer approximation algorithm. Finally, it is shown how the learned classifier can be incorporated into existing mixed integer optimization solvers. • A deep learning framework is proposed to decide when to use a decomposition. • A feature-based graph representation of optimization problems is proposed. • The proposed approach is applied to Mixed Integer Nonlinear optimization problems. • Integration of the proposed approach with optimization solvers is discussed. [ABSTRACT FROM AUTHOR]

In crowdsourcing systems, a challenge arises in efficiently recruiting workers with unknown execution speed to complete tasks with precedence constraints within the shortest possible time. Recent research either only studies recruiting unknown workers or focuses on assigning tasks with precedence constraints, but few works consider both these factors. This paper aims to address this challenge considering all these factors by proposing a digital twin-assisted Combinatorial Multi-arm bandit based multi-round work Recruitment and task Scheduling (CMRS) scheme. Firstly, with the help of digital twin technology, we build digital twin models for crowdsourcing tasks and workers in digital twin layer of platform. And we formulate a Multi-round Workers recruitment and Task scheduling with Precedence constraints (MWTP) problem with the object of minimizing task completion time (makespan) to model the above challenging issue in crowdsourcing computing. The MWTP problem can be divided into two sub-problems, the task scheduling sub-problem and the worker recruitment sub-problem. Secondly, in the CMRS scheme, the differential evolution based task scheduling (DETS) algorithm and CUCB-based worker recruitment (CWR) method are proposed to solve them, respectively. Specifically, for the task scheduling sub-problem, we first propose a priority-driven based task scheduling (PDTS) approximation algorithm to produce a primary solution with an explicit approximation ratio. Then a DETS algorithm is proposed to use the solution of PDTS for initialization and generate a better solution that further improves the performance. For the unknown workers recruitment sub-problem, we use the Combinatorial Multi-Arm Bandit framework to model this, and propose CWR method to learn the computational capabilities of workers while maintaining good performance during multiple rounds of worker recruitment by adding a tuning term to balanced exploration and exploitation. Finally, verified by extensive comparison experiments, the CMRS scheme can achieve the best performance of makespan compared with the baselines in most cases. [ABSTRACT FROM AUTHOR]

We present the Positional Knapsack Problem (PKP), show that it is NP-hard and admits a Fully Polynomial-Time Approximation Scheme (FPTAS). This problem is a variant of the classical Binary Knapsack Problem (KP) in which the contribution of an item to the objective function varies according to the position in which it is added. The change in the valuation adds new properties to the problem that do not hold for KP as PKP is not a generalization of KP. Our FPTAS is based on a dynamic programming algorithm and uses a recursive rounding approach, which is necessary since the objective function depends on each item's value and position. [ABSTRACT FROM AUTHOR]

In a delegation problem, a principal P with commitment power tries to pick one out of n options. Each option is drawn independently from a known distribution. Instead of inspecting the options herself, P delegates the information acquisition to a rational and self-interested agent A. After inspection, A proposes one of the options, and P can accept or reject. Delegation is a classic setting in economic information design with many prominent applications, but the computational problems are only poorly understood. In this paper, we study a natural online variant of delegation, in which the agent searches through the options in an online fashion. For each option, he has to irrevocably decide if he wants to propose the current option or discard it, before seeing information on the next option(s). How can we design algorithms for P that approximate the utility of her best option in hindsight? We show that in general P can obtain a Θ (1 / n) -approximation and extend this result to ratios of Θ (k / n) in case (1) A has a lookahead of k rounds, or (2) A can propose up to k different options. We provide fine-grained bounds independent of n based on three parameters. If the ratio of maximum and minimum utility for A is bounded by a factor α , we obtain an Ω (log ⁡ log ⁡ α / log ⁡ α) -approximation algorithm, and we show that this is best possible. Additionally, if P cannot distinguish options with the same value for herself, we show that ratios polynomial in 1 / α cannot be avoided. If there are at most β different utility values for A , we show a Θ (1 / β) -approximation. If the utilities of P and A for each option are related by a factor γ , we obtain an Ω (1 / log ⁡ γ) -approximation, where O (log ⁡ log ⁡ γ / log ⁡ γ) is best possible. [ABSTRACT FROM AUTHOR]

Internet of Things (IoT) services deployed across different Cloud Service Providers (CSPs) require seamless migration across heterogeneous clouds. Sky Computing (SC) facilitates the requirement by implementing a coordinator with communication APIs among clouds. However, security concerns of CSPs prevent the coordinator from accessing detailed cloud hardware information, thereby hindering the assessment of Serving Ability (SA) and exacerbating delays in service delivery. To ensure delay experience, we designed a loss-aware coordinator SkyCap for the multi-CSP collaboration in SC. First, to assess the SA of clouds with available information, we design a loss-aware SA assessment mechanism AdaSA that collects delay experience and Packet Loss Ratio (PLR) information for SA assessment. Since the uncontrollable PLR can increase service delay, we incorporate PLR as a disturbing factor in SA assessment to ensure a more precise evaluation. Second, to maximize the admission profit of the collaboration, we design two approximation algorithms within SkyCap to serve requests. Since the coordinator may deploy services in batches, we design a delay-aware offline algorithm AdaOff to serve requests simultaneously, while ensuring the computing capacity of clouds and the delay requirement of requests. Meanwhile, for asynchronously arriving requests, we design an ability-aware online algorithm AdaOn to serve requests in real-time, while guaranteeing the computing capacity of clouds, SA of clouds, and delay requirement of requests. Finally, extensive theoretical analysis and experimental validation confirm the performance of the coordinator SkyCap. The SA assessment mechanism AdaSA outperforms existing solutions in SA assessment by ensuring at most 1% deviation, especially in high-PLR scenarios. Meanwhile, the algorithm AdaOff exhibits a remarkable 20% improvement over the state-of-the-art in admission profit while ensuring stringent service delay. Concurrently, the algorithm AdaOn surpasses existing solutions, achieving a nearly 10% enhancement in both admission profit and service delay. In summary, the coordinator SkyCap stands out in theoretical groundwork and practical implementation, offering advancements in the SA assessment, admission profit, and service delay. [ABSTRACT FROM AUTHOR]

Discrete random variables are essential ingredients in various artificial intelligence problems. These include the estimation of the probability of missing the deadline in a series-parallel schedule and the assignment of suppliers to tasks in a project in a manner that maximizes the probability of meeting the overall project deadline. The solving of such problems involves repetitive operations, such as summation, over random variables. However, these computations are NP-hard. Therefore, we explore techniques and methods for approximating random variables with a given support size and minimal Kolmogorov distance. We examine both the general problem of approximating a random variable and a one-sided version in which over-approximation is allowed but not under-approximation. We propose several algorithms and evaluate their performance through computational complexity analysis and empirical evaluation. All the presented algorithms are optimal in the sense that given an input random variable and a requested support size, they return a new approximated random variable with the requested support size and minimal Kolmogorov distance from the input random variable. Our approximation algorithms offer useful estimations of probabilities in situations where exact computations are not feasible due to NP-hardness complexity. [ABSTRACT FROM AUTHOR]

The influence maximization problem asks to find a small number of early adopters of a product in a social network, such that the expected number of total adoptions is maximized over the network. The problem has been well-studied, but most of the studies focus on the case of a single product or purely competitive products. This paper proposes a new influence diffusion model for multiple complementary products, namely, the comparative linear threshold (Com-LT) model. Under the Com-LT model, we model the complementary relation by reducing the thresholds of nodes. With this model, we study two problems: SelfInfMax and CompInfMax. We prove that these two problems are both NP-Hard under the Com-LT model. For both the SelfInfMax and the CompInfMax problem, we theoretically analyze the monotonicity and submodularity, and accordingly leverage lower bound optimization to devise non-trivial effective approximation algorithms. We conduct experiments over 4 real-world datasets. The experimental results demonstrate the correctness and efficiency of the proposed algorithms. • We study the complementary version of the influence maximization problem. • We propose Com-LT model to describe the influence spread of non- competitive products. • We studied the SelfInfMax and the CompInfMax problem and show their hardness. • We propose approximation algorithms with high quality feasible solutions. • We conduct experiments on real networks and show the effectiveness of our algorithms. [ABSTRACT FROM AUTHOR]

This work considers to achieve near-optimal operation for a class of batch processes by employing self-optimizing control (SOC). Comparing with a continuous one, a batch process exhibits stronger nonlinearity with dynamics because of the non-steady operation condition. This necessitates a global version of SOC to achieve satisfactory performance. Meanwhile, it also makes the existing global SOC (gSOC) not directly applicable to batch processes due to the causality amongst variables. Therefore, it is necessary to extend the original gSOC to batch processes. In addition to the nonconvexity challenge of the original gSOC problem, the new extension for batch processes has to face even more challenges. Particularly, the causality due to dynamics of batch processes brings in structural constraints on controlled variables (CVs), making a CV selection problem even more difficult. To address these challenges, the gSOC problem is recast in a vectorized formulation and it is proved that the structural constraints considered are linear in the vectorized formulation. Moreover, a novel shortcut method is proposed to efficiently find sub-optimal but more transparent solutions for this problem. The effectiveness of the new approach is validated through a case study of a fed-batch reactor, where CVs are constructed through a combination matrix with a repetitive structure, resulting in a simple SOC scheme. This simplicity facilitates the implementation of the SOC approach and enhances its practical applicability and robustness. • Extends global SOC (gSOC) methodology to batch processes for the first time. • Proves certain structural constraints on CV combination matrix are linear. • Develops new convex approximation algorithm to solve gSOC with constraints. [ABSTRACT FROM AUTHOR]

Future cities promise to be more autonomous than ever, largely owing to our ability of coordinating complex systems in real time: fleets of self-driving cars will offer on-demand transportation services, delivery drones will fly parcels in our skies, power plants will provide renewable energy reliably. In many of these systems, there is no single decision-maker with full information and authority. Instead, the system performance greatly depends on the decisions made by interacting entities with local information and limited communication capabilities. Game theory, intended as the study of multi-agent decision-making, is a fitting paradigm to tackle many of the associated challenges. Moving from this observation, in this paper we review how tools and ideas from game theory can be brought to bear on the coordination of multi-agent systems. At the heart of the proposed approach is the design and influence of agents' preferences so that their local optimization induces a desirable system behavior. Its applicability spans a variety of settings irrespective of whether the decision makers are strategic (e.g., drivers in a road network), or not (e.g., delivery drones). Along the way, we also discuss future research directions and connections with related research areas including algorithmic game theory, incentive and mechanism design, economics, computational complexity, and approximation algorithms. [ABSTRACT FROM AUTHOR]

A directed hypergraph H = (V, A) is a finite set of vertices V and a set of hyper-arcs A , where each hyper-arc is an ordered pair of nonempty subsets of vertices. A flow hypergraph H = (V, A, s) is a triple, such that (V, A) is a directed hypergraph, s e V is a distinguished vertex such that s reaches every vertex of V. Reducible flow hypergraphs are a generalization of Hecht and Ullman's reducible flowgraphs. The feedback vertex set (fvs) decision problem has a directed hypergraph H and an integer k ≥ 0 as input and the question is whether there is V'⊆V, |V' |≤k such that H\V' is an acyclic directed hypergraph. It is known that fvs is polynomial time solvable for reducible flowgraphs. In this article we prove that fvs is NP-complete for reducible flow hypergraphs showing a reduction from 3-satisfiability problem with at most 3 occurrences per variable (3 sat3-). We exhibit a polynomial-time ∆-approximation for fvs in reducible flow hypergraphs, where ∆ is the maximum number of hyper-arcs adjacent to a vertex of H. [ABSTRACT FROM AUTHOR]

The length of a tree-decomposition of a graph is the maximum distance 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 maximum size of its isometric cycles. This work initiates the study of treelength in planar graphs by considering the next natural superclass of outerplanar 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 polynomial-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 infinite families of forbidden isometric subgraphs. [ABSTRACT FROM AUTHOR]

Biologists have proposed a vast list of problems heavily studied by mathematicians, computer scientists, and statisticians. From a theoretical point of view, biology can inspire exciting new problems when one is interested in estimating genetic modifications that occurred in the course of evolution. Structural modifications, such as genome rearrangements, are important for comparative genomics and they have led to many NP-hard problems. Reversal and Transposition are the most studied genome rearrangement events. To solve these problems, the gene order inside a genome is usually mapped into a permutation or a string. Permutations do not allow us to work with duplicate genes; in this case strings should be used. Problems with reversals and transpositions on permutations and strings are being studied since the 70s. Recently, studies start incorporating information regarding the size of the intergenic regions, which are genetic regions between each pair of consecutive genes inside the genome with a specific number of nucleotides. Problems can differ by changing the genetic information carried into the representation model, but all of them aim to transform a source genome into a target genome. In this work, we study the Sorting by Reversals with Flexible Intergenic Regions and Sorting by Reversals and Transpositions with Flexible Intergenic Regions problems on unsigned permutations. The goal is still to transform a source genome into the target genome, but turning the constraint less strict regarding the size of the intergenic regions on the target genome. We present a theoretical study showing that both problems are NP-hard and algorithms with constant approximation factor. [ABSTRACT FROM AUTHOR]

The input to a PPNC instance is integers n and p , and a non-negative real weighting of the edges of the clique K n on the vertex set {1,..., n }. We are asked to find a set of p disjoint cycles spanning {1,..., n } and subject to this such that the sum of the weights of the edges is minimized. We provide an efficient approximation algorithm for the metric version of this problem which has an approximation ratio of 4 if p ≤ n/5 and an approximation ratio of 51 for larger p. For p > n/5, our algorithm uses a subroutine which approximately solves the Mod 3 T -join With Slack problem. The input to an instance of Mod k T -join with Slack consists of integers n and B , a non-negative weighting of the edges of the clique K n , and a label l(v) from {0,1,..., k - 1} on each vertex of K n. We are asked to find the minimum weight spanning forest F from amongst those satisfying ∑ T∈F ((∑ v∈V(T) l(v)) mod k) ≤ B. If k = 2 and B = 0 this is the well-studied T -join problem which can be solved exactly in polynomial time. [ABSTRACT FROM AUTHOR]

Aiming at the problems in the existing white-feather broiler sound signal classification research, such as not considering the information and requirements in the real engineering application scenarios, not finding new applicable sound features, not providing the basis for the selection of classification learners, and the problems in the existing white-feather broiler sound signal filtering research, such as not carrying out in-depth research, not considering the signal characteristics, not analyzing the filtering effects in detail. Therefore, in this paper, the authors cleverly combined four methods of signal filtering, signal classification, machine learning, and sparse representation to propose a filtering and classification method for white-feather broiler sound signals based on sparse representation. Specifically, in terms of signal filtering, the signal characteristics of the white-feather broiler sound signal was carefully analyzed, a combination of noise reduction processing and signal reconstruction was newly proposed, and three classic and effective approximation algorithms were adopted, then the optimal filtering method of "using OMPA for noise reduction processing, and using 50-atom OMPA for signal reconstruction" was obtained. In terms of signal classification, in addition to the time-frequency domain and Mel-Frequency Cepstral Coefficients (abbr. MFCCs), time-frequency parameter features from sparse representations were newly extracted, and a total of 60-dimensional sound features were calculated on the frame signals, thus the data set was created. Feature engineering was performed on the data set, finally, the high-quality data set was obtained. Several common machine learning classification algorithms were used to train classification learners on the data set, and random forest with better performance was selected for parameter optimization. The parameter-optimized classification learner achieved the highest average prediction accuracy of 94.09%. Majority voting was newly proposed to process the prediction results to get the required signal classification result. On this basis, a new definition of classification accuracy suitable for white-feather broiler sound signals was newly proposed. Test results in real engineering application scenarios show that, the classification accuracy achieved by the proposed method on unknown white-feather broiler sound signals is about 88.89%. Compared with the existing research, the optimal filtering method considers the signal characteristics for the first time and achieves good filtering effects. The trained classification learner obtains excellent prediction effects and achieves good classification effects on several real sound types. This study is an important supplement to existing research on animal sound signal processing and classification, and provides important reference for the subsequent white-feather broiler health monitoring research. • Skillfully combine four methods to construct a signal processing and classification scheme. • Perform signal filtering based on sparse representation for the first time. • Use sparse representation to extract new time-frequency parameter features for the first time. • Obtain the optimal classification learner for white-feather broiler sound signal classification. • Newly propose the definition of classification accuracy for engineering application requirements. [ABSTRACT FROM AUTHOR]

This paper considers the high-dimensional table compression problem on balanced k -partite graph. The objective is to choose half of the vertices from each of the k -partite to maximize the total weight of edges connecting the chosen vertices. Our main contribution is a 0.8785-approximation algorithm for the high-dimensional table compression problem by introducing the α - i n d e p e n d e n t solutions through Lasserre semidefinite programming. This new algorithm improved two previous low-dimensional results, namely the 0.8731-approximation algorithm of Wu et al. for the one-dimensional case and the 0.6708-approximation of Xu and Du for the two-dimensional case. [Display omitted] • Present a 0.8785-approximation algorithm for high-dimensional table compression problem. • Obtain a group of independent optimal solutions through Lasserre hierarchy semidefinite programming. • The integer solutions to the original problem are obtained through deformed random hyperplane recognition. [ABSTRACT FROM AUTHOR]

• Optimal anechoic coating based on metagratings. • Meta-absorbers in low-frequency and broadband via subwavelength thicknesses. • Enhanced multiple scattering effects in tandem metagratings. • The theoretical model modulates local resonance coupling of multi-layer meta-units. The anechoic coating capable of absorbing sound energy in low frequency and broadband is essential to conceal underwater vehicles. In this work, metagrating has been demonstrated as a tunable quasi-perfect absorber in low frequency, which is constructed with the single layer viscoelastic medium embedded with the periodic cylindrical cavities and the steel plate. Upon effective medium approximation and genetic algorithm optimization, such tunable absorbers could be put forward via deep subwavelength thicknesses. Broadband underwater absorption would be further approached in the multi-layer metagratings while the longitudinal waves convert into shear waves efficiently via the local resonance coupling and multiple scattering effects. Distinct from previous studies that limit the configuration of anechoic coatings to a given law and inefficiently alter numerous geometric parameters for optimal acoustic performance, the metagrating comprising multi-layer voids with random periods is adopted to precisely modulate the surface impedance in the target spectrum, leading to quasi-perfect absorption performance in broadband. Our results will contribute to designing lightweight underwater absorbers to improve the stealth performance of vehicles. [Display omitted] [ABSTRACT FROM AUTHOR]

We introduce a new method for predicting the formation or the detection of unobserved links in real-world networks, which we refer to as the method of effective transitions. This method relies on the theory of isospectral matrix reductions to compute the probability of eventually transitioning from one vertex to another in a (biased) random walk on the network. This link prediction technique is quite versatile and can be used to predict links in networks that are directed or undirected and are either weighted or unweighted. We apply this method to a large number of social, technological, and natural networks and show that it is competitive with other link predictors, often outperforming them. We also provide a method of approximating our effective transition method and show that aside from having much lower temporal complexity, this approximation often provides more accurate predictions than the original effective transition method. We also prove a number of results regarding our effective transition algorithm and its approximation. [ABSTRACT FROM AUTHOR]

We consider several problems dealing with tracking of moving objects (e.g., vehicles) in networks. Given a graph G = (V , E) and two vertices s , t ∈ V , a set of vertices T ⊆ V is a tracking set for G (w.r.t. paths from s to t), if one can distinguish between any two paths from s to t by the order in which the vertices of T appear (or do not appear) in them. We prove that the problem of finding a minimum-cardinality tracking set w.r.t. shortest paths from s to t is NP-hard and even APX-hard. On the other hand, for the common case where G is planar, we present a 2-approximation algorithm for this problem. We also describe how to preprocess G (and its tracking set w.r.t. shortest paths from s to t), so that given a sequence of visited trackers, one can reconstruct the traversed path P in O (| P |) time. Moreover, we consider the following related problem: Given a graph G , two vertices s and t , and a set of forbidden vertices F ⊆ V − { s , t } , find a minimum-cardinality set of trackers V ∗ ⊂ V , such that a shortest path P from s to t passes through a forbidden vertex if and only if it passes through a vertex of V ∗. We present a polynomial-time (exact) algorithm for this problem. [ABSTRACT FROM AUTHOR]

We study the scheduling problem with calibrations. We are given a set of n jobs that need to be scheduled on a set of m machines. However, a machine can schedule jobs only if a calibration has been performed beforehand and the machine is considered as valid during a fixed time period of T , after which it must be recalibrated before running more jobs. In this paper, we investigate the batch calibrations; calibrations occur in batch and at the same moment. It is then not possible to perform any calibrations during a period of T. We consider different cost function depending on the number of machines we calibrate at a given time, i.e., the cost function is denoted as f (x) where x is the number of calibrations in the batch. Moreover, jobs have release time, deadline, and unit processing time. The objective is to schedule all jobs with the minimum cost of calibrations. We give a dynamic program to solve the case with an arbitrary cost function. Then, we propose several faster approximation algorithms for different cost functions: an optimal algorithm when f (x) = b , a 3-approximation algorithm when f (x) = x and a (m + b) / (b + 1) -approximation algorithm when f (x) = x + b. The running time of these algorithms are O (n 2). [ABSTRACT FROM AUTHOR]

For a graph G and a non-negative integral weight function w on the vertex set of G , a set S of vertices of G is w -safe if w (C) ≥ w (D) for every component C of the subgraph of G induced by S and every component D of the subgraph of G induced by the complement of S such that some vertex in C is adjacent to some vertex of D. The minimum weight w (S) of a w -safe set S is the safe number s (G , w) of the weighted graph (G , w) , and the minimum weight of a w -safe set that induces a connected subgraph of G is its connected safe number c s (G , w). Bapat et al. showed that computing c s (G , w) is NP-hard even when G is a star. For a given weighted tree (T , w) , they described a polynomial time 2-approximation algorithm for c s (T , w) as well as a polynomial time 4-approximation algorithm for s (T , w). Addressing a problem they posed, we present a PTAS for the connected safe number of a weighted tree. Our PTAS partly relies on an exact pseudopolynomial time algorithm, which also allows to derive an asymptotic FPTAS for restricted instances. Finally, we extend a bound due to Fujita et al. from trees to block graphs. [ABSTRACT FROM AUTHOR]

In this paper we study some generalizations of the parking permit problem (Meyerson, FOCS'05), in which we are given a demand r t ∈ { 0 , 1 } for instant of time t = 0 , ... , T − 1 , along with K permit types with lengths of time δ 1 , ... , δ K and sub-additive costs. A permit is a pair (k , t ˆ) ∈ K × Z + , and it covers interval t ˆ , t ˆ + δ k). We wish to find a minimum-cost set of permits that covers every t with r t = 1. Meyerson gave deterministic O (K) -competitive and randomized O (lg K) -competitive online algorithms for this problem, as well as matching lower bounds. The first variant we propose is the multi parking permit problem, in which an arbitrary demand is given at each instant ( r t ∈ Z + ) and we may buy multiple permits to serve it. We prove that the offline version of this problem can be solved in polynomial time, and we show how to reduce it to the parking permit problem, while losing a constant cost factor. This approximation-preserving reduction yields a deterministic O (K) -competitive online algorithm and a randomized O (lg K) -competitive online algorithm. For a leasing variant of the Steiner network problem, these results imply a O (lg n) -approximation algorithm and a O (lg K lg | V |) -competitive online algorithm, where n is the number of requests and | V | is the size of the input metric. The second variant we propose is the group parking permit problem, in which we also have an arbitrary demand for each instant, and each permit of type k can be either a single permit, costing γ k and covering one demand per instant of time, or a group permit, which costs M ⋅ γ k for some constant M ≥ 1 and covers an arbitrary number of demands in the interval covered by this permit. (I.e., group permits have infinite capacity.) For this version of the problem, we give an 8-approximation algorithm and a deterministic O (K) -competitive online algorithm. The first result yields an improvement on the previous best approximation algorithm for the leasing version of the rent-or-buy problem. Finally, we study the 2D parking permit problem, proposed by Hu, Ludwig, Richa and Schmid (2015), in which a permit type is defined by a length of time and an integer capacity. They presented a constant approximation algorithm and a deterministic O (K) -competitive online algorithm for a hierarchical version of the problem, but those algorithms have pseudo-polynomial running time. We show how to turn their algorithms into polynomial time algorithms. Moreover, these results yield approximation and competitive online algorithms for a hierarchical leasing version of the buy-at-bulk network design problem. We also show that their original pseudo-polynomial offline algorithm works for a more general version of the 2D parking permit problem, which we prove to be NP-hard. [ABSTRACT FROM AUTHOR]

We consider the numerical method for fractional diffusion problems which is based on an extension to a mixed boundary value problem for a local operator in a higher dimensional space. We observe that, when this problem is discretized using tensor product spaces as is commonly done, the solution can be very well approximated by low-rank tensors; we provide some analysis to support this observation. This fact motivates us to apply iterative low-rank approximation algorithms in order to efficiently solve this extended problem. In particular, we employ a recently proposed greedy Tucker approximation method as well as a more classical greedy rank one update method. Throughout, all objects of interest are kept in suitable low-rank approximations, which dramatically reduces the required amount of memory compared to the full formulation of the extended problem. Our approach can be used for general, non-structured space discretizations. If the space discretization itself has tensor product structure, we can further decompose the problem in order to deal with even lower-dimensional objects. We also note that the approach can be directly applied to higher-order discretizations both in space and the extended variable. A further contribution of our work is a rank one version of a diagonal preconditioner which can mitigate the severe ill-conditioning of the extended problem arising due to mesh grading and singularity of the coefficient. This preconditioner can be realized using a simple pre- and postprocessing step and does not affect the computational effort of our algorithm. In several numerical examples, we demonstrate the convergence behavior of the proposed methods. In particular, the Tucker approximation approach requires only a few iterations in order to reach the discretization error in all tested settings. [ABSTRACT FROM AUTHOR]

In recent years, a number of numerical methods for the solution of fractional Laplace and, more generally, fractional diffusion problems have been proposed. The approaches are quite diverse and include, among others, the use of best uniform rational approximations, quadrature for Dunford–Taylor-like integrals, finite element approaches for a localized elliptic extension into a space of increased dimensions, and time stepping methods for a parabolic reformulation of the fractional differential equation. A systematic comparison, both theoretical and experimental, of these approaches has thus far been lacking. A main contribution of the present work is the observation that all approaches mentioned above can, in fact, be interpreted as realizing different rational approximations of a univariate function over the spectrum of the original (non-fractional) diffusion operator. While this is obvious for some of the methods, it is a new result in particular for extension-based and time stepping approaches. This observation allows us to cast all described methods into a unified theoretical and computational framework, which has a number of benefits. Theoretically, it enables us to develop new convergence proofs for several of the studied methods, clarifies similarities and differences between the approaches, suggests how to design new and improved methods, and allows a direct comparison of the relative performance of the various methods. Practically, it provides a single, simple to implement, efficient and fully parallel algorithm for the realization of all studied methods; for instance, this immediately yields a fast and memory-efficient way of realizing all tensor product extension methods and lets us parallelize the otherwise inherently sequential time stepping approach. Finally, we present a detailed numerical study comparing all investigated methods for various fractional exponents and draw conclusions from the results. The comparison is made fair by the central insight that the computational effort of all these methods depends only on a single parameter, the degree of the underlying rational approximation. As a point of comparison, we also test a simple rational approximation method based on a black-box direct rational approximation algorithm which performs very well in practice. [ABSTRACT FROM AUTHOR]

We consider the maximum (weight) independent set problem in unit disk graphs. The high complexity of the existing polynomial-time approximation schemes motivated the development of faster constant approximation algorithms. In this paper, we present a 2.16-approximation algorithm that runs in O (n log 2 n) time and a 2-approximation algorithm that runs in O (n 2 log n) time for the unweighted version of the problem. In the weighted version, the running times increase by an O (log n) factor. Our algorithms are based on a classic strip decomposition, but we improve over previous algorithms by efficiently using geometric data structures. We also propose a PTAS for the unweighted version. [ABSTRACT FROM AUTHOR]

In this paper, we give randomized approximation algorithms for stochastic cumulative VRPs for the split and unsplit deliveries. The approximation ratios are max { 1 + 1. 5 α , 3 } and 6, respectively, where α is the approximation ratio for the metric TSP. The approximation factor is further reduced for trees. These results extend the results in Anupam Gupta et al. (2012) and Daya Ram Gaur et al. (2013). The bounds reported here improve the bounds in Daya Ram Gaur et al. (2016). [ABSTRACT FROM AUTHOR]

Let there be a set M of m parallel machines and a set J of n jobs, where each job j takes p i , j time units on machine M i. In makespan minimization the goal is to schedule each job non-preemptively on a machine such that the length of the schedule, the makespan, is minimum. We investigate a generalization of makespan minimization on unrelated parallel machines (R | | C m a x) where J is partitioned into b bags B = (B 1 , ... , B b) , and no two jobs belonging to the same bag can be scheduled on the same machine. First we present a simple b -approximation algorithm for R | | C m a x with bags (R | b a g | C m a x). We also give a polynomial-time approximation scheme (PTAS) for R | b a g | C m a x with machine types where both the number of machine types and bags are constant; two machines M i and M i ′ have the same machine type if p i , j = p i ′ , j for all j ∈ J. This result infers the existence of a PTAS for uniform parallel machines (Q | b a g | C m a x) when the number of machine speeds and number of bags are both constant. Then, we present a b / 2 -approximation algorithm for the graph balancing problem with b ≥ 2 bags; the approximation ratio is tight for b = 3 , unless P = NP , and this algorithm solves the graph balancing problem with b = 2 bags in polynomial time. In addition, we present a polynomial-time algorithm for the restricted assignment problem on uniform parallel machines with bags when all the jobs have unit length. To complement our algorithmic results, we show that when the jobs have lengths 1 or 2 it is NP -hard to approximate the optimum makespan within a factor smaller than 3/2 for both the restricted assignment and graph balancing problems with b = 2 bags and b = 3 bags, respectively. We also prove that Q | b a g | C m a x with b = 2 bags is strongly NP -hard. [ABSTRACT FROM AUTHOR]

This paper is devoted to the distributed complexity of finding an approximation of the maximum cut (MaxCut) in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communication and achieves an approximation ratio of at least 1 2 in expectation. When the graph is d -regular and triangle-free, a slightly better approximation ratio can be achieved with a randomized algorithm running in a single round. Here, we investigate the round complexity of deterministic distributed algorithms for MaxCut in regular graphs. We first prove that if G is d -regular, with d even and fixed, no deterministic algorithm running in a constant number of rounds can achieve a constant approximation ratio. We then give a simple one-round deterministic algorithm achieving an approximation ratio of 1 d for d -regular graphs when d is odd. We show that this is best possible in several ways, and in particular no deterministic algorithm with approximation ratio 1 d + ϵ (with ϵ > 0) can run in a constant number of rounds. We also prove results of a similar flavor for the MaxDiCut problem in regular oriented graphs, where we want to maximize the number of arcs oriented from the left part to the right part of the cut. [ABSTRACT FROM AUTHOR]