OpenRaiser/Intern-Atlas huggingface dataset:
Diversity and Social Network Structure in Collective Decision Making: Evolutionary Perspectives with Agent-Based Simulations
Venue: arXiv cs.MA 2019
Year: 2019

Collective, especially group-based, managerial decision making is crucial in organizations. Using an evolutionary theoretic approach to collective decision making, agent-based simulations were conducted to investigate how human collective decision making would be affected by the agents' diversity in problem understanding and/or behavior in discussion, as well as by their social network structure. Simulation results indicated that groups with consistent problem understanding tended to produce higher utility values of ideas and displayed better decision convergence, but only if there was no group-level bias in collective problem understanding. Simulation results also indicated the importance of balance between selection-oriented (i.e., exploitative) and variation-oriented (i.e., explorative) behaviors in discussion to achieve quality final decisions. Expanding the group size and introducing non-trivial social network structure generally improved the quality of ideas at the cost of decision convergence. Simulations with different social network topologies revealed collective decision making on small-world networks with high local clustering tended to achieve highest decision quality more often than on random or scale-free networks. Implications of this evolutionary theory and simulation approach for future managerial research on collective, group, and multi-level decision making are discussed.
Spanning Properties of Yao and $Θ$-Graphs in the Presence of Constraints
Venue: arXiv cs.CG 2019
Year: 2019

We present improved upper bounds on the spanning ratio of constrained $θ$-graphs with at least 6 cones and constrained Yao-graphs with 5 or at least 7 cones. Given a set of points in the plane, a Yao-graph partitions the plane around each vertex into $m$ disjoint cones, each having aperture $θ= 2 π/m$, and adds an edge to the closest vertex in each cone. Constrained Yao-graphs have the additional property that no edge properly intersects any of the given line segment constraints. Constrained $θ$-graphs are similar to constrained Yao-graphs, but use a different method to determine the closest vertex. We present tight bounds on the spanning ratio of a large family of constrained $θ$-graphs. We show that constrained $θ$-graphs with $4k + 2$ ($k \geq 1$ and integer) cones have a tight spanning ratio of $1 + 2 \sin(θ/2)$, where $θ$ is $2 π/ (4k + 2)$. We also present improved upper bounds on the spanning ratio of the other families of constrained $θ$-graphs. These bounds match the current upper bounds in the unconstrained setting. We also show that constrained Yao-graphs with an even number of cones ($m \geq 8$) have spanning ratio at most $1 / ( 1 - 2 \sin (θ/2) )$ and constrained Yao-graphs with an odd number of cones ($m \geq 5$) have spanning ratio at most $1 / ( 1 - 2 \sin (3θ/8) )$. As is the case with constrained $θ$-graphs, these bounds match the current upper bounds in the unconstrained setting, which implies that like in the unconstrained setting using more cones can make the spanning ratio worse.
Decentralized Goal Assignment and Safe Trajectory Generation in Multi-Robot Networks via Multiple Lyapunov Functions
Venue: arXiv cs.MA 2019
Year: 2019

This paper considers the problem of decentralized goal assignment and trajectory generation for multi-robot networks when only local communication is available, and proposes an approach based on methods related to switched systems and set invariance. A family of Lyapunov-like functions is employed to encode the (local) decision making among candidate goal assignments, under which a group of connected agents chooses the assignment that results in the shortest total distance to the goals. An additional family of Lyapunov-like barrier functions is activated in the case when the optimal assignment may lead to colliding trajectories, maintaining thus system safety while preserving the convergence guarantees. The proposed switching strategies give rise to feedback control policies that are computationally efficient and scalable with the number of agents, and therefore suitable for applications including first-response deployment of robotic networks under limited information sharing. The efficacy of the proposed method is demonstrated via simulation results and experiments with six ground robots.
A Generic Numbering System based on Catalan Families of Combinatorial Objects
Venue: arXiv cs.MS 2019
Year: 2019

We describe arithmetic algorithms on a canonical number representation based on the Catalan family of combinatorial objects specified as a Haskell type class. Our algorithms work on a {\em generic} representation that we illustrate on instances members of the Catalan family, like ordered binary and multiway trees. We validate the correctness of our algorithms by defining an instance of the same type class based the usual bitstring-based natural numbers. While their average and worst case complexity is within constant factors of their traditional counterparts, our algorithms provide super-exponential gains for numbers corresponding to Catalan objects of low representation size.
Nash Equilbria for Quadratic Voting
Venue: arXiv cs.GT 2019
Year: 2019

Voters making a binary decision purchase votes from a centralized clearing house, paying the square of the number of votes purchased. The net payoff to an agent with utility $u$ who purchases $v$ votes is $Ψ(S_{n+1})u-v^{2}$, where $Ψ$ is a monotone function taking values between -1 and +1 and $S_{n+1}$ is the sum of all votes purchased by the $n+1$ voters participating in the election. The utilities of the voters are assumed to arise by random sampling from a probability distribution $F_{U}$ with compact support; each voter knows her own utility, but not those of the other voters, although she does know the sampling distribution $F_{U}$. Nash equilibria for this game are described. These results imply that the expected inefficiency of any Nash equilibrium decays like $1/n$.
A Framework for a Smart Social Blood Donation System Based on Mobile Cloud Computing
Venue: arXiv cs.CY 2019
Year: 2019

Blood Donation and Blood Transfusion Services (BTS) are crucial for saving people lives. Recently, worldwide efforts have been undertaken to utilize social media and smartphone applications to make the blood donation process more convenient, offer additional services, and create communities around blood donation centers. Blood banks suffer frequent shortage of blood; hence, advertisements are frequently seen on social networks urging healthy individuals to donate blood for patients who urgently require blood transfusion. The blood donation process usually consumes a lot of time and effort from both donors and medical staff since there is no concrete information system that allows donors and blood donation centers communicate efficiently and coordinate with each other to minimize time and effort required for blood donation process. Moreover, most blood banks work in isolation and are not integrated with other blood donation centers and health organizations which affect the blood donation and blood transfusion services quality. This work aims at developing a Blood Donation System (BDS) based on the cutting-edge information technologies of cloud computing and mobile computing.
Relative Entailment Among Probabilistic Implications
Venue: arXiv cs.LO 2019
Year: 2019

We study a natural variant of the implicational fragment of propositional logic. Its formulas are pairs of conjunctions of positive literals, related together by an implicational-like connective; the semantics of this sort of implication is defined in terms of a threshold on a conditional probability of the consequent, given the antecedent: we are dealing with what the data analysis community calls confidence of partial implications or association rules. Existing studies of redundancy among these partial implications have characterized so far only entailment from one premise and entailment from two premises, both in the stand-alone case and in the case of presence of additional classical implications (this is what we call "relative entailment"). By exploiting a previously noted alternative view of the entailment in terms of linear programming duality, we characterize exactly the cases of entailment from arbitrary numbers of premises, again both in the stand-alone case and in the case of presence of additional classical implications. As a result, we obtain decision algorithms of better complexity; additionally, for each potential case of entailment, we identify a critical confidence threshold and show that it is, actually, intrinsic to each set of premises and antecedent of the conclusion.
Proof Normalisation in a Logic Identifying Isomorphic Propositions
Venue: arXiv cs.LO 2019
Year: 2019

We define a fragment of propositional logic where isomorphic propositions, such as $A\land B$ and $B\land A$, or $A\Rightarrow (B\land C)$ and $(A\Rightarrow B)\land(A\Rightarrow C)$ are identified. We define System I, a proof language for this logic, and prove its normalisation and consistency.
Robust Transmission Network Expansion Planning under Correlated Uncertainty
Venue: arXiv cs.CE 2019
Year: 2019

This paper addresses the transmission network expansion planning problem under uncertain demand and generation capacity. A two-stage adaptive robust optimization framework is adopted whereby the worst-case operating cost is accounted for under a given user-defined uncertainty set. This work differs from previously reported robust solutions in two respects. First, the typically disregarded correlation of uncertainty sources is explicitly considered through an ellipsoidal uncertainty set relying on their variance-covariance matrix. In addition, we describe the analogy between the corresponding second-stage problem and a certain class of mathematical programs arising in structural reliability. This analogy gives rise to a relevant probabilistic interpretation of the second stage, thereby revealing an undisclosed feature of the worst-case setting characterizing robust optimization with ellipsoidal uncertainty sets. More importantly, a novel nested decomposition approach based on results from structural reliability is devised to solve the proposed robust counterpart, which is cast as an instance of mixed-integer trilevel programming. Numerical results from several case studies demonstrate that the effect of correlated uncertainty can be captured by the proposed robust approach.
A $(1 + {\varepsilon})$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
Venue: arXiv cs.DS 2019
Year: 2019

Graphs with bounded highway dimension were introduced by Abraham et al. [SODA 2010] as a model of transportation networks. We show that any such graph can be embedded into a distribution over bounded treewidth graphs with arbitrarily small distortion. More concretely, given a weighted graph G = (V, E) of constant highway dimension, we show how to randomly compute a weighted graph H = (V, E') that distorts shortest path distances of G by at most a 1 + ${\varepsilon}$ factor in expectation, and whose treewidth is polylogarithmic in the aspect ratio of G. Our probabilistic embedding implies quasi-polynomial time approximation schemes for a number of optimization problems that naturally arise in transportation networks, including Travelling Salesman, Steiner Tree, and Facility Location. To construct our embedding for low highway dimension graphs we extend Talwar's [STOC 2004] embedding of low doubling dimension metrics into bounded treewidth graphs, which generalizes known results for Euclidean metrics. We add several non-trivial ingredients to Talwar's techniques, and in particular thoroughly analyse the structure of low highway dimension graphs. Thus we demonstrate that the geometric toolkit used for Euclidean metrics extends beyond the class of low doubling metrics.
On the Likelihood of Single-Peaked Preferences
Venue: arXiv cs.GT 2019
Year: 2019

This paper contains an extensive combinatorial analysis of the single-peaked domain restriction and investigates the likelihood that an election is single-peaked. We provide a very general upper bound result for domain restrictions that can be defined by certain forbidden configurations. This upper bound implies that many domain restrictions (including the single-peaked restriction) are very unlikely to appear in a random election chosen according to the Impartial Culture assumption. For single-peaked elections, this upper bound can be refined and complemented by a lower bound that is asymptotically tight. In addition, we provide exact results for elections with few voters or candidates. Moreover, we consider the Pólya urn model and the Mallows model and obtain lower bounds showing that single-peakedness is considerably more likely to appear for certain parameterizations.
Diffusion Methods for Classification with Pairwise Relationships
Venue: arXiv cs.DS 2019
Year: 2019

We define two algorithms for propagating information in classification problems with pairwise relationships. The algorithms are based on contraction maps and are related to non-linear diffusion and random walks on graphs. The approach is also related to message passing algorithms, including belief propagation and mean field methods. The algorithms we describe are guaranteed to converge on graphs with arbitrary topology. Moreover they always converge to a unique fixed point, independent of initialization. We prove that the fixed points of the algorithms under consideration define lower-bounds on the energy function and the max-marginals of a Markov random field. The theoretical results also illustrate a relationship between message passing algorithms and value iteration for an infinite horizon Markov decision process. We illustrate the practical application of the algorithms under study with numerical experiments in image restoration, stereo depth estimation and binary classification on a grid.
Atomic Scheduling of Appliance Energy Consumption in Residential Smart Grid
Venue: arXiv cs.NI 2019
Year: 2019

The current formulation of the optimal scheduling of appliance energy consumption uses as optimization variables the vectors of appliances' scheduled energy consumption over equally-divided time slots of a day, which does not take into account the atomicity of appliances' operations (i.e., the unsplittable nature of appliances' operations and resulting energy consumption). In this paper, we provide a new formulation of atomic scheduling of energy consumption based on the optimal routing framework; the flow configurations of users over multiple paths between the common source and destination nodes of a ring network are used as optimization variables, which indicate the starting times of scheduled energy consumption, and optimal scheduling problems are now formulated in terms of the user flow configurations. Because the atomic optimal scheduling results in a Boolean-convex problem for a convex objective function, we propose a successive convex relaxation technique for efficient calculation of an approximate solution, where we iteratively drop fractional-valued elements and apply convex relaxation to the resulting problem until we find a feasible suboptimal solution. Numerical results for the cost and peak-to-average ratio minimization problems demonstrate that the successive convex relaxation technique can provide solutions close to, often identical to, global optimal solutions.
Generalized Majorization-Minimization
Venue: arXiv cs.CV 2019
Year: 2019

Non-convex optimization is ubiquitous in machine learning. Majorization-Minimization (MM) is a powerful iterative procedure for optimizing non-convex functions that works by optimizing a sequence of bounds on the function. In MM, the bound at each iteration is required to \emph{touch} the objective function at the optimizer of the previous bound. We show that this touching constraint is unnecessary and overly restrictive. We generalize MM by relaxing this constraint, and propose a new optimization framework, named Generalized Majorization-Minimization (G-MM), that is more flexible. For instance, G-MM can incorporate application-specific biases into the optimization procedure without changing the objective function. We derive G-MM algorithms for several latent variable models and show empirically that they consistently outperform their MM counterparts in optimizing non-convex objectives. In particular, G-MM algorithms appear to be less sensitive to initialization.
Approximation Algorithm for Minimum Weight $(k,m)$-CDS Problem in Unit Disk Graph
Venue: arXiv cs.DM 2019
Year: 2019

In a wireless sensor network, the virtual backbone plays an important role. Due to accidental damage or energy depletion, it is desirable that the virtual backbone is fault-tolerant. A fault-tolerant virtual backbone can be modeled as a $k$-connected $m$-fold dominating set ($(k,m)$-CDS for short). In this paper, we present a constant approximation algorithm for the minimum weight $(k,m)$-CDS problem in unit disk graphs under the assumption that $k$ and $m$ are two fixed constants with $m\geq k$. Prior to this work, constant approximation algorithms are known for $k=1$ with weight and $2\leq k\leq 3$ without weight. Our result is the first constant approximation algorithm for the $(k,m)$-CDS problem with general $k,m$ and with weight. The performance ratio is $(α+2.5kρ)$ for $k\geq 3$ and $(α+2.5ρ)$ for $k=2$, where $α$ is the performance ratio for the minimum weight $m$-fold dominating set problem and $ρ$ is the performance ratio for the subset $k$-connected subgraph problem (both problems are known to have constant performance ratios.)
Continuous control with deep reinforcement learning
Venue: arXiv cs.LG 2019
Year: 2019

We adapt the ideas underlying the success of Deep Q-Learning to the continuous action domain. We present an actor-critic, model-free algorithm based on the deterministic policy gradient that can operate over continuous action spaces. Using the same learning algorithm, network architecture and hyper-parameters, our algorithm robustly solves more than 20 simulated physics tasks, including classic problems such as cartpole swing-up, dexterous manipulation, legged locomotion and car driving. Our algorithm is able to find policies whose performance is competitive with those found by a planning algorithm with full access to the dynamics of the domain and its derivatives. We further demonstrate that for many of the tasks the algorithm can learn policies end-to-end: directly from raw pixel inputs.
Shared Memory Pipelined Parareal
Venue: arXiv cs.MS 2019
Year: 2019

For the parallel-in-time integration method Parareal, pipelining can be used to hide some of the cost of the serial correction step and improve its efficiency. The paper introduces a basic OpenMP implementation of pipelined Parareal and compares it to a standard MPI-based variant. Both versions yield almost identical runtimes, but, depending on the compiler, the OpenMP variant consumes about 7% less energy and has a significantly smaller memory footprint. However, its higher implementation complexity might make it difficult to use in legacy codes and in combination with spatial parallelisation.
Critical Behavior and Universality Classes for an Algorithmic Phase Transition in Sparse Reconstruction
Venue: arXiv cs.IT 2019
Year: 2019

Recovery of an $N$-dimensional, $K$-sparse solution $\mathbf{x}$ from an $M$-dimensional vector of measurements $\mathbf{y}$ for multivariate linear regression can be accomplished by minimizing a suitably penalized least-mean-square cost $||\mathbf{y}-\mathbf{H} \mathbf{x}||_2^2+λV(\mathbf{x})$. Here $\mathbf{H}$ is a known matrix and $V(\mathbf{x})$ is an algorithm-dependent sparsity-inducing penalty. For `random' $\mathbf{H}$, in the limit $λ\rightarrow 0$ and $M,N,K\rightarrow \infty$, keeping $ρ=K/N$ and $α=M/N$ fixed, exact recovery is possible for $α$ past a critical value $α_c = α(ρ)$. Assuming $\mathbf{x}$ has iid entries, the critical curve exhibits some universality, in that its shape does not depend on the distribution of $\mathbf{x}$. However, the algorithmic phase transition occurring at $α=α_c$ and associated universality classes remain ill-understood from a statistical physics perspective, i.e. in terms of scaling exponents near the critical curve. In this article, we analyze the mean-field equations for two algorithms, Basis Pursuit ($V(\mathbf{x})=||\mathbf{x}||_{1} $) and Elastic Net ($V(\mathbf{x})= ||\mathbf{x}||_{1} + \tfrac{g}{2} ||\mathbf{x}||_{2}^2$) and show that they belong to different universality classes in the sense of scaling exponents, with Mean Squared Error (MSE) of the recovered vector scaling as $λ^\frac{4}{3}$ and $λ$ respectively, for small $λ$ on the critical line. In the presence of additive noise, we find that, when $α>α_c$, MSE is minimized at a non-zero value for $λ$, whereas at $α=α_c$, MSE always increases with $λ$.
Fair Cake-Cutting among Families
Venue: arXiv cs.GT 2019
Year: 2019

We study the fair division of a continuous resource, such as a land-estate or a time-interval, among pre-specified groups of agents, such as families. Each family is given a piece of the resource and this piece is used simultaneously by all family members, while different members may have different value functions. Three ways to assess the fairness of such a division are examined. (a) Average Fairness means that each family's share is fair according to the "family value function", defined as the arithmetic mean of the value functions of the family members. (b) Unanimous Fairness means that all members in all families feel that their family's share is fair according to their personal value function. (c) Democratic Fairness means that in each family, at least a fixed fraction (e.g. a half) of the members feel that their family's share is fair. We compare these criteria based on the number of connected components in the resulting division and on their compatibility with Pareto-efficiency.
Operator scaling: theory and applications
Venue: arXiv cs.CC 2019
Year: 2019

In this paper we present a deterministic polynomial time algorithm for testing if a symbolic matrix in non-commuting variables over $\mathbb{Q}$ is invertible or not. The analogous question for commuting variables is the celebrated polynomial identity testing (PIT) for symbolic determinants. In contrast to the commutative case, which has an efficient probabilistic algorithm, the best previous algorithm for the non-commutative setting required exponential time (whether or not randomization is allowed). The algorithm efficiently solves the "word problem" for the free skew field, and the identity testing problem for arithmetic formulae with division over non-commuting variables, two problems which had only exponential-time algorithms prior to this work. The main contribution of this paper is a complexity analysis of an existing algorithm due to Gurvits, who proved it was polynomial time for certain classes of inputs. We prove it always runs in polynomial time. The main component of our analysis is a simple (given the necessary known tools) lower bound on central notion of capacity of operators (introduced by Gurvits). We extend the algorithm to actually approximate capacity to any accuracy in polynomial time, and use this analysis to give quantitative bounds on the continuity of capacity (the latter is used in a subsequent paper on Brascamp-Lieb inequalities). Symbolic matrices in non-commuting variables, and the related structural and algorithmic questions, have a remarkable number of diverse origins and motivations. They arise independently in (commutative) invariant theory and representation theory, linear algebra, optimization, linear system theory, quantum information theory, approximation of the permanent and naturally in non-commutative algebra. We provide a detailed account of some of these sources and their interconnections.