An official website of the United States government
Linear computation broadcast (LCBC) refers to a setting with d dimensional data stored at a central server, where K users, each with some prior linear side-information, wish to compute various linear combinations of the data. For each computation instance, the data is represented as a d-dimensional vector with elements in a finite field Fpn where pn is a power of a prime. The computation is to be performed many times, and the goal is to determine the minimum amount of information per computation instance that must be broadcast to satisfy all the users. The reciprocal of the optimal broadcast cost per computation instance is the capacity of LCBC. The capacity is known for up to K = 3 users. Since LCBC includes index coding as a special case, large K settings of LCBC are at least as hard as the index coding problem. As such the general LCBC problem is beyond our reach and we do not pursue it. Instead of the general setting (all cases), by focusing on the generic setting (almost all cases) this work shows that the generic capacity of the symmetric LCBC (where every user has m′ dimensions of side-information and m dimensions of demand) for large number of users (K ≥ d suffices) is Cg = 1/∆g, where ∆g = min{ max{0, d − m' }, dm/(m+m′)}, is the broadcast cost that is both achievable and unbeatable asymptotically almost surely for large n, among all LCBC instances with the given parameters p, K, d, m, m′. Relative to baseline schemes of random coding or separate transmissions, Cg shows an extremal gain by a factor of K as a function of number of users, and by a factor of ≈ d/4 as a function of data dimensions, when optimized over remaining parameters. For arbitrary number of users, the generic capacity of the symmetric LCBC is characterized within a factor of 2.
more »
« less
An Efficient Solving Approach for the p‐Dispersion Problem Based on the Distance‐Based Spatially Informed Property
Thep‐dispersion problem is a spatial optimization problem that aims to maximize the minimum separation distance among all assigned nodes. This problem is characterized by an innate spatial structure based on distance attributes. This research proposes a novel approach, named thedistance‐based spatially informed property(D‐SIP) method to reduce the problem size of thep‐dispersion instances, facilitating a more efficient solution while maintaining optimality in nearly all cases. The D‐SIP is derived from investigating the underlying spatial characteristics from the behaviors of thep‐dispersion problem in determining the optimal location of nodes. To define the D‐SIP, this research applies Ripley'sK‐function to the different types of point patterns, given that the optimal solutions of thep‐dispersion problem are strongly associated with the spatial proximity among points discovered by Ripley'sK‐function. The results demonstrate that the D‐SIP identifies collective dominances of optimal solutions, leading to buildingthe spatially informed p‐dispersion model. The simulation‐based experiments show that the proposed method significantly diminishes the size of problems, improves computational performance, and secures optimal solutions for 99.9% of instances (999 out of 1,000 instances) under diverse conditions.
more »
« less
- Award ID(s):
- 1951344
- PAR ID:
- 10492043
- Publisher / Repository:
- Wiley-Blackwell
- Date Published:
- Journal Name:
- Geographical Analysis
- ISSN:
- 0016-7363
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Staphylococcus aureus(S. aureus), a common foodborne pathogen, poses significant public health challenges due to its association with various infectious diseases. A key player in its pathogenicity, which is the IsdA protein, is an essential virulence factor inS. aureusinfections. In this work, we present an integrated in‐silico and experimental approach using MD simulations and surface plasmon resonance (SPR)‐based aptasensing measurements to investigateS. aureusbiorecognition via IsdA surface protein binding. SPR, a powerful real‐time and label‐free technique, was utilized to characterize interaction dynamics between the aptamer and IsdA protein, and MD simulations was used to characterize the stable and dynamic binding regions. By characterizing and optimizing pivotal parameters such as aptamer concentration and buffer conditions, we determined the aptamer's binding performance. Under optimal conditions of pH 7.4 and 150 mM NaCl concentration, the kinetic parameters were determined;ka = 3.789 × 104/Ms,kd = 1.798 × 103/s, andKD = 4.745 × 10−8 M. The simulations revealed regions of interest in the IsdA‐aptamer complex. Region I, which includes interactions between amino acid residues H106 and R107 and nucleotide residues 9G, 10U, 11G and 12U of the aptamer, had the strongest interaction, based on ΔG and B‐factor values, and hence contributed the most to the stability of the interaction. Region II, which covers residue 37A reflects the dynamic nature of the interaction due to frequent contacts. The approach presents a rigorous characterization of aptamer‐IsdA binding behavior, supporting the potential application of the IsdA‐binding aptamer system forS. aureusbiosensing.more » « less
-
Abstract The CO2flux () from lakes to the atmosphere is a large component of the global carbon cycle and depends on the air–water CO2concentration gradient (ΔCO2) and the gas transfer velocity (k). Both ΔCO2andkcan vary on multiple timescales and understanding their contributions to is important for explaining variability in fluxes and developing optimal sampling designs. We measured and ΔCO2and derivedkfor one full ice‐free period in 18 lakes using floating chambers and estimated the contributions of ΔCO2andkto variability. Generally,kcontributed more than ΔCO2to short‐term (1–9 d) variability. With increased temporal period, the contribution ofkto variability decreased, and in some lakes resulted in ΔCO2contributing more thankto variability over the full ice‐free period. Increased contribution of ΔCO2to variability over time occurred across all lakes but was most apparent in large‐volume southern‐boreal lakes and in deeper (> 2 m) parts of lakes, whereaskwas linked to variability in shallow waters. Accordingly, knowing the variability of bothkand ΔCO2over time and space is needed for accurate modeling of from these variables. We conclude that priority in assessments should be given to direct measurements of at multiple sites when possible, or otherwise from spatially distributed measurements of ΔCO2combined withk‐models that incorporate spatial variability of lake thermal structure and meteorology.more » « less
-
null (Ed.)We study the problem of learning Ising models in a setting where some of the samples from the underlying distribution can be arbitrarily corrupted. In such a setup, we aim to design statistically optimal estimators in a high-dimensional scaling in which the number of nodes p, the number of edges k and the maximal node degree d are allowed to increase to infinity as a function of the sample size n. Our analysis is based on exploiting moments of the underlying distribution, coupled with novel reductions to univariate estimation. Our proposed estimators achieve an optimal dimension independent dependence on the fraction of corrupted data in the contaminated setting, while also simultaneously achieving high-probability error guarantees with optimal sample-complexity. We corroborate our theoretical results by simulations.more » « less
-
Purpose Marine transportation has been faced with an increasing demand for containerized cargo during the past decade. Marine container terminals (MCTs), as the facilities for connecting seaborne and inland transportation, are expected to handle the increasing amount of containers, delivered by vessels. Berth scheduling plays an important role for the total throughput of MCTs as well as the overall effectiveness of the MCT operations. This study aims to propose a novel island-based metaheuristic algorithm to solve the berth scheduling problem and minimize the total cost of serving the arriving vessels at the MCT. Design/methodology/approach A universal island-based metaheuristic algorithm (UIMA) was proposed in this study, aiming to solve the spatially constrained berth scheduling problem. The UIMA population was divided into four sub-populations (i.e. islands). Unlike the canonical island-based algorithms that execute the same metaheuristic on each island, four different population-based metaheuristics are adopted within the developed algorithm to search the islands, including the following: evolutionary algorithm (EA), particle swarm optimization (PSO), estimation of distribution algorithm (EDA) and differential evolution (DE). The adopted population-based metaheuristic algorithms rely on different operators, which facilitate the search process for superior solutions on the UIMA islands. Findings The conducted numerical experiments demonstrated that the developed UIMA algorithm returned near-optimal solutions for the small-size problem instances. As for the large-size problem instances, UIMA was found to be superior to the EA, PSO, EDA and DE algorithms, which were executed in isolation, in terms of the obtained objective function values at termination. Furthermore, the developed UIMA algorithm outperformed various single-solution-based metaheuristic algorithms (including variable neighborhood search, tabu search and simulated annealing) in terms of the solution quality. The maximum UIMA computational time did not exceed 306 s. Research limitations/implications Some of the previous berth scheduling studies modeled uncertain vessel arrival times and/or handling times, while this study assumed the vessel arrival and handling times to be deterministic. Practical implications The developed UIMA algorithm can be used by the MCT operators as an efficient decision support tool and assist with a cost-effective design of berth schedules within an acceptable computational time. Originality/value A novel island-based metaheuristic algorithm is designed to solve the spatially constrained berth scheduling problem. The proposed island-based algorithm adopts several types of metaheuristic algorithms to cover different areas of the search space. The considered metaheuristic algorithms rely on different operators. Such feature is expected to facilitate the search process for superior solutions.more » « less
