亚洲男人的天堂2018av,欧美草比,久久久久久免费视频精选,国色天香在线看免费,久久久久亚洲av成人片仓井空

Many real-world optimization problems contain unknown parameters that must be predicted prior to solving. To train the predictive machine learning (ML) models involved, the commonly adopted approach focuses on maximizing predictive accuracy. However, this approach does not always lead to the minimization of the downstream task loss. Decision-focused learning (DFL) is a recently proposed paradigm whose goal is to train the ML model by directly minimizing the task loss. However, state-of-the-art DFL methods are limited by the assumptions they make about the structure of the optimization problem (e.g., that the problem is linear) and by the fact that can only predict parameters that appear in the objective function. In this work, we address these limitations by instead predicting \textit{distributions} over parameters and adopting score function gradient estimation (SFGE) to compute decision-focused updates to the predictive model, thereby widening the applicability of DFL. Our experiments show that by using SFGE we can: (1) deal with predictions that occur both in the objective function and in the constraints; and (2) effectively tackle two-stage stochastic optimization problems.

This paper presents a decentralized algorithm for solving distributed convex optimization problems in dynamic networks with time-varying objectives. The unique feature of the algorithm lies in its ability to accommodate a wide range of communication systems, including previously unsupported ones, by abstractly modeling the information exchange in the network. Specifically, it supports a novel communication protocol based on the "over-the-air" function computation (OTA-C) technology, that is designed for an efficient and truly decentralized implementation of the consensus step of the algorithm. Unlike existing OTA-C protocols, the proposed protocol does not require the knowledge of network graph structure or channel state information, making it particularly suitable for decentralized implementation over ultra-dense wireless networks with time-varying topologies and fading channels. Furthermore, the proposed algorithm synergizes with the "superiorization" methodology, allowing the development of new distributed algorithms with enhanced performance for the intended applications. The theoretical analysis establishes sufficient conditions for almost sure convergence of the algorithm to a common time-invariant solution for all agents, assuming such a solution exists. Our algorithm is applied to a real-world distributed random field estimation problem, showcasing its efficacy in terms of convergence speed, scalability, and spectral efficiency. Furthermore, we present a superiorized version of our algorithm that achieves faster convergence with significantly reduced energy consumption compared to the unsuperiorized algorithm.

\textit{Pursuit-evasion games} have been intensively studied for several decades due to their numerous applications in artificial intelligence, robot motion planning, database theory, distributed computing, and algorithmic theory. \textsc{Cops and Robber} (\CR) is one of the most well-known pursuit-evasion games played on graphs, where multiple \textit{cops} pursue a single \textit{robber}. The aim is to compute the \textit{cop number} of a graph, $k$, which is the minimum number of cops that ensures the \textit{capture} of the robber. From the viewpoint of parameterized complexity, \CR is W[2]-hard parameterized by $k$~[Fomin et al., TCS, 2010]. Thus, we study structural parameters of the input graph. We begin with the \textit{vertex cover number} ($\mathsf{vcn}$). First, we establish that $k \leq \frac{\mathsf{vcn}}{3}+1$. Second, we prove that \CR parameterized by $\mathsf{vcn}$ is \FPT by designing an exponential kernel. We complement this result by showing that it is unlikely for \CR parameterized by $\mathsf{vcn}$ to admit a polynomial compression. We extend our exponential kernels to the parameters \textit{cluster vertex deletion number} and \textit{deletion to stars number}, and design a linear vertex kernel for \textit{neighborhood diversity}. Additionally, we extend all of our results to several well-studied variations of \CR.

This work, for the first time, introduces two constant factor approximation algorithms with linear query complexity for non-monotone submodular maximization over a ground set of size $n$ subject to a knapsack constraint, $\mathsf{DLA}$ and $\mathsf{RLA}$. $\mathsf{DLA}$ is a deterministic algorithm that provides an approximation factor of $6+\epsilon$ while $\mathsf{RLA}$ is a randomized algorithm with an approximation factor of $4+\epsilon$. Both run in $O(n \log(1/\epsilon)/\epsilon)$ query complexity. The key idea to obtain a constant approximation ratio with linear query lies in: (1) dividing the ground set into two appropriate subsets to find the near-optimal solution over these subsets with linear queries, and (2) combining a threshold greedy with properties of two disjoint sets or a random selection process to improve solution quality. In addition to the theoretical analysis, we have evaluated our proposed solutions with three applications: Revenue Maximization, Image Summarization, and Maximum Weighted Cut, showing that our algorithms not only return comparative results to state-of-the-art algorithms but also require significantly fewer queries.

Building on two recent models of [Almalki and Michail, 2022] and [Gupta et al., 2023], we explore the constructive power of a set of geometric growth processes. The studied processes, by applying a sequence of centralized, parallel, and linear-strength growth operations, can construct shapes from smaller shapes or from a singleton exponentially fast. A technical challenge in growing shapes that fast is the need to avoid collisions caused, for example, when the shape breaks, stretches, or self-intersects. We distinguish two types of growth operations -- one that avoids collisions by preserving cycles and one that achieves the same by breaking them -- and two types of graph models. We study the following types of shape reachability questions in these models. Given a class of initial shapes $\mathcal{I}$ and a class of final shapes $\mathcal{F}$, our objective is to determine whether any (some) shape $S \in \mathcal{F}$ can be reached from any shape $S_0 \in \mathcal{I}$ in a number of time steps which is (poly)logarithmic in the size of $S$. For the reachable classes, we additionally present the respective growth processes. In cycle-preserving growth, we study these problems in basic classes of shapes such as paths, spirals, and trees and reveal the importance of the number of turning points as a parameter. We give both positive and negative results. For cycle-breaking growth, we obtain a strong positive result -- a general growth process that can grow any connected shape from a singleton fast.

In submodular $k$-partition, the input is a non-negative submodular function $f$ defined over a finite ground set $V$ (given by an evaluation oracle) along with a positive integer $k$ and the goal is to find a partition of the ground set $V$ into $k$ non-empty parts $V_1, V_2, ..., V_k$ in order to minimize $\sum_{i=1}^k f(V_i)$. Narayanan, Roy, and Patkar (Journal of Algorithms, 1996) designed an algorithm for submodular $k$-partition based on the principal partition sequence and showed that the approximation factor of their algorithm is $2$ for the special case of graph cut functions (subsequently rediscovered by Ravi and Sinha (Journal of Operational Research, 2008)). In this work, we study the approximation factor of their algorithm for three subfamilies of submodular functions -- monotone, symmetric, and posimodular, and show the following results: 1. The approximation factor of their algorithm for monotone submodular $k$-partition is $4/3$. This result improves on the $2$-factor achievable via other algorithms. Moreover, our upper bound of $4/3$ matches the recently shown lower bound under polynomial number of function evaluation queries (Santiago, IWOCA 2021). Our upper bound of $4/3$ is also the first improvement beyond $2$ for a certain graph partitioning problem that is a special case of monotone submodular $k$-partition. 2. The approximation factor of their algorithm for symmetric submodular $k$-partition is $2$. This result generalizes their approximation factor analysis beyond graph cut functions. 3. The approximation factor of their algorithm for posimodular submodular $k$-partition is $2$. We also construct an example to show that the approximation factor of their algorithm for arbitrary submodular functions is $\Omega(n/k)$.

Given a graph $G=(V,E)$, for a vertex set $S\subseteq V$, let $N(S)$ denote the set of vertices in $V$ that have a neighbor in $S$. Extending the concept of binding number of graphs by Woodall~(1973), for a vertex set $X \subseteq V$, we define the binding number of $X$, denoted by $\bind(X)$, as the maximum number $b$ such that for every $S \subseteq X$ where $N(S)\neq V(G)$ it holds that $|N(S)|\ge b {|S|}$. Given this definition, we prove that if a graph $V(G)$ contains a subset $X$ with $\bind(X)= 1/k$ where $k$ is an integer, then $G$ possesses a matching of size at least $|X|/(k+1)$. Using this statement, we derive tight bounds for the estimators of the matching size in planar graphs. These estimators are previously used in designing sublinear space algorithms for approximating the maching size in the data stream model of computation. In particular, we show that the number of locally superior vertices is a $3$ factor approximation of the matching size in planar graphs. The previous analysis by Jowhari (2023) proved a $3.5$ approximation factor. As another application, we show a simple variant of an estimator by Esfandiari \etal (2015) achieves $3$ factor approximation of the matching size in planar graphs. Namely, let $s$ be the number of edges with both endpoints having degree at most $2$ and let $h$ be the number of vertices with degree at least $3$. We prove that when the graph is planar, the size of matching is at least $(s+h)/3$. This result generalizes a known fact that every planar graph on $n$ vertices with minimum degree $3$ has a matching of size at least $n/3$.

In this work, we study massive multiple-input multiple-output (MIMO) precoders optimizing power consumption while achieving the users' rate requirements. We first characterize analytically the solutions for narrowband and wideband systems minimizing the power amplifiers (PAs) consumption in low system load, where the per-antenna power constraints are not binding. After, we focus on the asymptotic wideband regime. The power consumed by the whole base station (BS) and the high-load scenario are then also investigated. We obtain simple solutions, and the optimal strategy in the asymptotic case reduces to finding the optimal number of active antennas, relying on known precoders among the active antennas. Numerical results show that large savings in power consumption are achievable in the narrowband system by employing antenna selection, while all antennas need to be activated in the wideband system when considering only the PAs consumption, and this implies lower savings. When considering the overall BS power consumption and a large number of subcarriers, we show that significant savings are achievable in the low-load regime by using a subset of the BS antennas. While optimization based on transmit power pushes to activate all antennas, optimization based on consumed power activates a number of antennas proportional to the load.

Electroencephalogram (EEG) signals reflect brain activity across different brain states, characterized by distinct frequency distributions. Through multifractal analysis tools, we investigate the scaling behaviour of different classes of EEG signals and artifacts. We show that brain states associated to sleep and general anaesthesia are not in general characterized by scale invariance. The lack of scale invariance motivates the development of artifact removal algorithms capable of operating independently at each scale. We examine here the properties of the wavelet quantile normalization algorithm, a recently introduced adaptive method for real-time correction of transient artifacts in EEG signals. We establish general results regarding the regularization properties of the WQN algorithm, showing how it can eliminate singularities introduced by artefacts, and we compare it to traditional thresholding algorithms. Furthermore, we show that the algorithm performance is independent of the wavelet basis. We finally examine its continuity and boundedness properties and illustrate its distinctive non-local action on the wavelet coefficients through pathological examples.

Maximum weight independent set (MWIS) admits a $\frac1k$-approximation in inductively $k$-independent graphs and a $\frac{1}{2k}$-approximation in $k$-perfectly orientable graphs. These are a a parameterized class of graphs that generalize $k$-degenerate graphs, chordal graphs, and intersection graphs of various geometric shapes such as intervals, pseudo-disks, and several others. We consider a generalization of MWIS to a submodular objective. Given a graph $G=(V,E)$ and a non-negative submodular function $f: 2^V \rightarrow \mathbb{R}_+$, the goal is to approximately solve $\max_{S \in \mathcal{I}_G} f(S)$ where $\mathcal{I}_G$ is the set of independent sets of $G$. We obtain an $\Omega(\frac1k)$-approximation for this problem in the two mentioned graph classes. The first approach is via the multilinear relaxation framework and a simple contention resolution scheme, and this results in a randomized algorithm with approximation ratio at least $\frac{1}{e(k+1)}$. This approach also yields parallel (or low-adaptivity) approximations. Motivated by the goal of designing efficient and deterministic algorithms, we describe two other algorithms for inductively $k$-independent graphs that are inspired by work on streaming algorithms: a preemptive greedy algorithm and a primal-dual algorithm. In addition to being simpler and faster, these algorithms, in the monotone submodular case, yield the first deterministic constant factor approximations for various special cases that have been previously considered such as intersection graphs of intervals, disks and pseudo-disks.