consider:looking-to-see   648
[1712.08573] Longest common substring with approximately $k$ mismatches
In the longest common substring problem we are given two strings of length n and must find a substring of maximal length that occurs in both strings. It is well-known that the problem can be solved in linear time, but the solution is not robust and can vary greatly when the input strings are changed even by one letter. To circumvent this, Leimeister and Morgenstern introduced the problem of the longest common substring with k mismatches. Lately, this problem has received a lot of attention in the literature. In this paper we first show a conditional lower bound based on the SETH hypothesis implying that there is little hope to improve existing solutions. We then introduce a new but closely related problem of the longest common substring with approximately k mismatches and use computational geometry techniques to show that it admits a solution with strongly subquadratic running time. We also apply these results to obtain a strongly subquadratic approximation algorithm for the longest common substring with k mismatches problem and show conditional hardness of improving its approximation ratio.
strings  computational-complexity  algorithms  rather-interesting  nudge-targets  consider:looking-to-see
4 days ago by Vaguery
[1711.08903] Tilings of convex sets by mutually incongruent equilateral triangles contain arbitrarily small tiles
We show that every tiling of a convex set in the Euclidean plane ℝ2 by equilateral triangles of mutually different sizes contains arbitrarily small tiles. The proof is purely elementary up to the discussion of one family of tilings of the full plane ℝ2, which is based on a surprising connection to a random walk on a directed graph.
combinatorics  tiling  constraint-satisfaction  rather-interesting  consider:looking-to-see  to-write-about
4 days ago by Vaguery
[1710.07145] Reaching a Target in the Plane with no Information
A mobile agent has to reach a target in the Euclidean plane. Both the agent and the target are modeled as points. In the beginning, the agent is at distance at most D>0 from the target. Reaching the target means that the agent gets at a {\em sensing distance} at most r>0 from it. The agent has a measure of length and a compass. We consider two scenarios: in the {\em static} scenario the target is inert, and in the {\em dynamic} scenario it may move arbitrarily at any (possibly varying) speed bounded by v. The agent has no information about the parameters of the problem, in particular it does not know D, r or v. The goal is to reach the target at lowest possible cost, measured by the total length of the trajectory of the agent.
Our main result is establishing the minimum cost (up to multiplicative constants) of reaching the target under both scenarios, and providing the optimal algorithm for the agent. For the static scenario the minimum cost is Θ((logD+log1r)D2/r), and for the dynamic scenario it is Θ((logM+log1r)M2/r), where M=max(D,v). Under the latter scenario, the speed of the agent in our algorithm grows exponentially with time, and we prove that for an agent whose speed grows only polynomially with time, this cost is impossible to achieve.
agent-based  optimization  mathematical-recreations  planning  algorithms  nudge-targets  consider:looking-to-see
4 days ago by Vaguery
[1709.04380] Neural Network Based Nonlinear Weighted Finite Automata
Weighted finite automata (WFA) can expressively model functions defined over strings but are inherently linear models. Given the recent successes of nonlinear models in machine learning, it is natural to wonder whether ex-tending WFA to the nonlinear setting would be beneficial. In this paper, we propose a novel model of neural network based nonlinearWFA model (NL-WFA) along with a learning algorithm. Our learning algorithm is inspired by the spectral learning algorithm for WFAand relies on a nonlinear decomposition of the so-called Hankel matrix, by means of an auto-encoder network. The expressive power of NL-WFA and the proposed learning algorithm are assessed on both synthetic and real-world data, showing that NL-WFA can lead to smaller model sizes and infer complex grammatical structures from data.
formal-languages  automata  rather-interesting  neural-networks  representation  statistics  modeling  to-write-about  consider:looking-to-see
4 days ago by Vaguery
Chopping a square into 7 triangles with almost the same area It's impossible...
It's impossible to divide a square into an odd number of triangles with the same area. This amazing result was proved by Paul Monsky in 1970, but I only heard about it today, from +David Eppstein, here on G+.

So it's impossible. But you can still try your best! These are the two best tries with 7 triangles and at most 8 vertices. These were discovered last year by Jean-Philippe Labbé, Günter Rote, and Günter Ziegler. They used a lot of clever math and programming to do this
mathematical-recreations  plane-geometry  nudge-targets  consider:looking-to-see
4 days ago by Vaguery
[1801.03534] Mechanical Computing Systems Using Only Links and Rotary Joints
A new paradigm for mechanical computing is demonstrated that requires only two basic parts, links and rotary joints. These basic parts are combined into two main higher level structures, locks and balances, and suffice to create all necessary combinatorial and sequential logic required for a Turing-complete computational system. While working systems have yet to be implemented using this new paradigm, the mechanical simplicity of the systems described may lend themselves better to, e.g., microfabrication, than previous mechanical computing designs. Additionally, simulations indicate that if molecular-scale implementations could be realized, they would be far more energy-efficient than conventional electronic computers.
out-of-the-box  computation  representation  not-quite-far-enough  nudge-targets  consider:looking-to-see
4 days ago by Vaguery
[1609.06349] A review of matrix scaling and Sinkhorn's normal form for matrices and positive maps
Given a nonnegative matrix A, can you find diagonal matrices D1, D2 such that D1AD2 is doubly stochastic? The answer to this question is known as Sinkhorn's theorem. It has been proved with a wide variety of methods, each presenting a variety of possible generalisations. Recently, generalisations such as to positive maps between matrix algebras have become more and more interesting for applications. This text gives a review of over 70 years of matrix scaling. The focus lies on the mathematical landscape surrounding the problem and its solution as well as the generalisation to positive maps and contains hardly any nontrivial unpublished results.
matrices  algorithms  to-write-about  nudge-targets  consider:looking-to-see  easily-checked
21 days ago by Vaguery
[1712.05390] Partisan gerrymandering with geographically compact districts
Bizarrely shaped voting districts are frequently lambasted as likely instances of gerrymandering. In order to systematically identify such instances, researchers have devised several tests for so-called geographic compactness (i.e., shape niceness). We demonstrate that under certain conditions, a party can gerrymander a competitive state into geographically compact districts to win an average of over 70% of the districts. Our results suggest that geometric features alone may fail to adequately combat partisan gerrymandering.
computational-geometry  politics  multiobjective-optimization  rather-interesting  to-write-about  consider:looking-to-see  nudge-targets  consider:stochastic-versions
24 days ago by Vaguery
Continued Fractions
I like con­tin­ued frac­tions for their elegance, their finite closure under a wider set of oper­a­tions than dec­imal expan­sion, and their most-sig­nif­icant-part-first arithmetic. But they run for unpre­dictable and pos­si­bly non-ter­minat­ing time before pro­vid­ing any informa­tion at all.
I pro­pose that a useful real-number rep­re­senta­tion would be equiv­a­lent to inter­vals that could be narrowed by applying a compu­ta­tion. Con­tin­ued frac­tions are such a narrow­ing inter­val: truncat­ing at an odd number of val­ues gives a lower bound, while truncat­ing at an even number gives an upper bound. The prob­lem is that not every answer gives such a narrow­ing inter­val because not all con­tin­ued frac­tions con­tin­ue. [1; 2, 2, …] is a narrow­ing inter­val, but [2], it’s square, must appear in an all-or-noth­ing way.
All of which begs the ques­tion, what rep­re­senta­tion should be used? It clearly will not be canon­ical, since we want to be able to rep­re­sent two as both an finite inte­ger and an infi­nitely-narrow­ing inter­val converg­ing on two. Beyond that, it isn’t clear. Some­thing to think about.
continued-fractions  algorithms  arithmetic  to-write-about  nudge-targets  consider:looking-to-see
29 days ago by Vaguery
Arithmetic with Continued Fractions
Multiprecision arithmetic algorithms usually represent real numbers as decimals, or perhaps as their base-2n analogues. But this representation has some puzzling properties. For example, there is no exact representation of even as simple a number as one-third. Continued fractions are a practical but little-known alternative.

Continued fractions are a representation of the real numbers that are in many ways more mathematically natural than the usual decimal or binary representations. All rational numbers have simple representations, and so do many irrational numbers, such as sqrt(2) and e1. One reason that continued fractions are not often used, however, is that it's not clear how to involve them in basic operations like addition and multiplication. This was an unsolved problem until 1972, when Bill Gosper found practical algorithms for continued fraction arithmetic.

In this talk, I explain what continued fractions are and why they are interesting, how to represent them in computer programs, and how to calculate with them.
29 days ago by Vaguery
[1708.04215] A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation.
Our techniques build upon the constant-factor approximation algorithm for the special case of node-weighted metrics. Specifically, we give a generic reduction to structured instances that resemble but are more general than those arising from node-weighted metrics. For those instances, we then solve Local-Connectivity ATSP, a problem known to be equivalent (in terms of constant-factor approximation) to the asymmetric traveling salesman problem.
algorithms  via:vielmetti  operations-research  approximation  optimization  computational-complexity  to-write-about  nudge-targets  consider:looking-to-see
6 weeks ago by Vaguery
[1703.07856] Testing for the Equality of two Distributions on High Dimensional Object Spaces
Energy statistics are estimators of the energy distance that depend on the distances between observations. The idea behind energy statistics is to consider a statistical potential energy that would parallel Newton's gravitational potential energy. This statistical potential energy is zero if and only if a certain null hypothesis relating two distributions holds true. In Szekely and Rizzo(2004), a nonparametric test for equality of two multivariate distributions was given, based on the Euclidean distance between observations. This test was shown to be effective for high dimensional multivariate data, and was implemented by an appropriate distribution free permutation test. As an extension of Szekely and Rizzo (2013), here we consider the energy distance between to independent random objects X and Y on the object space M, that admits an embedding into an Euclidean space. In the case of a Kendall shape space, we can use its VW-embedding into an Euclidean space of matrices and define the extrinsic distance between two shapes as their VW associated distance. The corresponding energy distance between two distributions of Kendall shapes of k-ads will be called VW-energy distance We test our methodology on, to compare the distributions of Kendall shape of the contour of the midsagittal section of the Corpus Callossum in normal vs ADHD diagnosed individuals. Here we use the VW distance between the shapes of two children CC midsections. Using the CC data coming originally from this http URL 1000.projects.nitrc.org/indi/adhd200/ it appears that the two Kendall shape distributions are not significantly different.
classification  feature-construction  rather-interesting  computer-vision  representation  algorithms  nudge-targets  consider:rediscovery  consider:looking-to-see
7 weeks ago by Vaguery
[1708.08691] Extremal solutions to some art gallery and terminal-pairability problems
The chosen tool of this thesis is an extremal type approach. The lesson drawn by the theorems proved in the thesis is that surprisingly small compromise is necessary on the efficacy of the solutions to make the approach work. The problems studied have several connections to other subjects and practical applications.
The first part of the thesis is concerned with orthogonal art galleries. A sharp extremal bound is proved on partitioning orthogonal polygons into at most 8-vertex polygons using established techniques in the field of art gallery problems. This fills in the gap between already known results for partitioning into at most 6- and 10-vertex orthogonal polygons.
Next, these techniques are further developed to prove a new type of extremal art gallery result. The novelty provided by this approach is that it establishes a connection between mobile and stationary guards. This theorem has strong computational consequences, in fact, it provides the basis for an 83-approximation algorithm for guarding orthogonal polygons with rectangular vision.
In the second part, the graph theoretical concept of terminal-pairability is studied in complete and complete grid graphs. Once again, the extremal approach is conductive to discovering efficient methods to solve the problem.
In the case of a complete base graph, the new demonstrated lower bound on the maximum degree of realizable demand graphs is 4 times higher than previous best results. The techniques developed are then used to solve the classical extremal edge number problem for the terminal-pairability problem in complete base graphs.
The complete grid base graph lies on the other end of the spectrum in terms density amongst path-pairable graphs. It is shown that complete grid graphs are relatively efficient in routing edge-disjoint paths.
computational-geometry  combinatorics  plane-geometry  extreme-values  rather-interesting  to-write-about  nudge-targets  consider:approximation  consider:looking-to-see
9 weeks ago by Vaguery
[1706.01557] The minimum Manhattan distance and minimum jump of permutations
Let π be a permutation of {1,2,…,n}. If we identify a permutation with its graph, namely the set of n dots at positions (i,π(i)), it is natural to consider the minimum L1 (Manhattan) distance, d(π), between any pair of dots. The paper computes the expected value of d(π) when n→∞ and π is chosen uniformly, and settles a conjecture of Bevan, Homberger and Tenner (motivated by permutation patterns), showing that when d is fixed and n→∞, the probability that d(π)≥d+2 tends to e−d2−d.
The minimum jump 𝗆𝗃(π) of π, defined by 𝗆𝗃(π)=min1≤i≤n−1|π(i+1)−π(i)|, is another natural measure in this context. The paper computes the expected value of 𝗆𝗃(π), and the asymptotic probability that 𝗆𝗃(π)≥d+1 for any constant d.
combinatorics  probability-theory  permutations  rather-interesting  to-write-about  to-simulate  nudge-targets  consider:looking-to-see
9 weeks ago by Vaguery
[1610.06934] The K Shortest Paths Problem with Application to Routing
Due to the computational complexity of finding almost shortest simple paths, we propose that identifying a larger collection of (nonbacktracking) paths is more efficient than finding almost shortest simple paths on positively weighted real-world networks. First, we present an easy to implement O(mlogm+kL) solution for finding all (nonbacktracking) paths with bounded length D between two arbitrary nodes on a positively weighted graph, where L is an upperbound for the number of nodes in any of the k outputted paths. Subsequently, we illustrate that for undirected Chung-Lu random graphs, the ratio between the number of nonbacktracking and simple paths asymptotically approaches 1 with high probability for a wide range of parameters. We then consider an application to the almost shortest paths algorithm to measure path diversity for internet routing in a snapshot of the Autonomous System graph subject to an edge deletion process.
planning  data-structures  algorithms  rather-interesting  operations-research  graph-theory  to-write-about  nudge-targets  consider:looking-to-see
9 weeks ago by Vaguery
[1711.03172] Curve Reconstruction via the Global Statistics of Natural Curves
Reconstructing the missing parts of a curve has been the subject of much computational research, with applications in image inpainting, object synthesis, etc. Different approaches for solving that problem are typically based on processes that seek visually pleasing or perceptually plausible completions. In this work we focus on reconstructing the underlying physically likely shape by utilizing the global statistics of natural curves. More specifically, we develop a reconstruction model that seeks the mean physical curve for a given inducer configuration. This simple model is both straightforward to compute and it is receptive to diverse additional information, but it requires enough samples for all curve configurations, a practical requirement that limits its effective utilization. To address this practical issue we explore and exploit statistical geometrical properties of natural curves, and in particular, we show that in many cases the mean curve is scale invariant and often times it is extensible. This, in turn, allows to boost the number of examples and thus the robustness of the statistics and its applicability. The reconstruction results are not only more physically plausible but they also lead to important insights on the reconstruction problem, including an elegant explanation why certain inducer configurations are more likely to yield consistent perceptual completions than others.
inference  computer-vision  rather-interesting  algorithms  nudge-targets  consider:looking-to-see  consider:representation  performance-measure  to-write-about
9 weeks ago by Vaguery
[1704.07422] Iterative Methods for Photoacoustic Tomography in Attenuating Acoustic Media
The development of efficient and accurate reconstruction methods is an important aspect of tomographic imaging. In this article, we address this issue for photoacoustic tomography. To this aim, we use models for acoustic wave propagation accounting for frequency dependent attenuation according to a wide class of attenuation laws that may include memory. We formulate the inverse problem of photoacoustic tomography in attenuating medium as an ill-posed operator equation in a Hilbert space framework that is tackled by iterative regularization methods. Our approach comes with a clear convergence analysis. For that purpose we derive explicit expressions for the adjoint problem that can efficiently be implemented. In contrast to time reversal, the employed adjoint wave equation is again damping and, thus has a stable solution. This stability property can be clearly seen in our numerical results. Moreover, the presented numerical results clearly demonstrate the Efficiency and accuracy of the derived iterative reconstruction algorithms in various situations including the limited view case.
tomography  numerical-methods  inverse-problems  rather-interesting  signal-processing  algorithms  nudge-targets  consider:benchmarking  consider:looking-to-see
9 weeks ago by Vaguery
[1705.01887] Streaming for Aibohphobes: Longest Palindrome with Mismatches
A palindrome is a string that reads the same as its reverse, such as "aibohphobia" (fear of palindromes). Given an integer d>0, a d-near-palindrome is a string of Hamming distance at most d from its reverse. We study the natural problem of identifying a longest d-near-palindrome in data streams. The problem is relevant to the analysis of DNA databases, and to the task of repairing recursive structures in documents such as XML and JSON. We present an algorithm that returns a d-near-palindrome whose length is within a multiplicative (1+ϵ)-factor of the longest d-near-palindrome. Our algorithm also returns the set of mismatched indices of the d-near-palindrome, using (dlog7nϵlog(1+ϵ)) bits of space, and (dlog6nϵlog(1+ϵ)) update time per arriving symbol. We show that Ω(dlogn) space is necessary for estimating the length of longest d-near-palindromes with high probability. We further obtain an additive-error approximation algorithm and a comparable lower bound, as well as an exact two-pass algorithm that solves the longest d-near-palindrome problem using (d2n‾√log6n) bits of space.
strings  computational-complexity  algorithms  probability-theory  inference  online-learning  rather-interesting  to-write-about  nudge-targets  consider:looking-to-see  consider:representation
9 weeks ago by Vaguery
[1609.07531] Popular Matchings with Multiple Partners
Our input is a bipartite graph G=(A∪B,E) where each vertex in A∪B has a preference list strictly ranking its neighbors. The vertices in A and in B are called students and courses, respectively. Each student a seeks to be matched to 𝖼𝖺𝗉(a)≥1 courses while each course b seeks 𝖼𝖺𝗉(b)≥1 many students to be matched to it. The Gale-Shapley algorithm computes a pairwise-stable matching (one with no blocking edge) in G in linear time. We consider the problem of computing a popular matching in G -- a matching M is popular if M cannot lose an election to any matching where vertices cast votes for one matching versus another. Our main contribution is to show that a max-size popular matching in G can be computed by the 2-level Gale-Shapley algorithm in linear time. This is an extension of the classical Gale-Shapley algorithm and we prove its correctness via linear programming.
operations-research  combinatorics  optimization  computational-complexity  algorithms  heuristics  nudge-targets  consider:looking-to-see  to-write-about  consider:comparing-to-random
10 weeks ago by Vaguery
[1710.00104] Small Satellite Constellation Separation using Linear Programming based Differential Drag Commands
We study the optimal control of an arbitrarily large constellation of small satellites operating in low Earth orbit. Simulating the lack of on-board propulsion, we limit our actuation to the use of differential drag maneuvers to make in-plane changes to the satellite orbits. We propose an efficient method to separate a cluster of satellites into a desired constellation shape while respecting actuation constraints and maximizing the operational lifetime of the constellation. By posing the problem as a linear program, we solve for the optimal drag commands for each of the satellites on a daily basis with a shrinking-horizon model predictive control approach. We then apply this control strategy in a nonlinear orbital dynamics simulation with a simple, varying atmospheric density model. We demonstrate the ability to control a cluster of 100+ satellites starting at the same initial conditions in a circular low Earth orbit to form an equally spaced constellation (with a relative angular separation error tolerance of one-tenth a degree). The constellation separation task can be executed in 71 days, a time frame that is competitive for the state-of-the-practice. This method allows us to trade the time required to converge to the desired constellation with a sacrifice in the overall constellation lifetime, measured as the maximum altitude loss experienced by one of the satellites in the group after the separation maneuvers.
nonlinear-dynamics  control-theory  rather-interesting  simulation  nudge-targets  consider:coordination  consider:looking-to-see  to-write-about
10 weeks ago by Vaguery

Copy this bookmark:

description:

tags: