**consider:looking-to-see**648

[1712.08573] Longest common substring with approximately $k$ mismatches

4 days ago by Vaguery

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

4 days ago by Vaguery

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

4 days ago by Vaguery

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
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.

4 days ago by Vaguery

[1709.04380] Neural Network Based Nonlinear Weighted Finite Automata

4 days ago by Vaguery

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...

4 days ago by Vaguery

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
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

4 days ago by Vaguery

[1801.03534] Mechanical Computing Systems Using Only Links and Rotary Joints

4 days ago by Vaguery

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

21 days ago by Vaguery

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

24 days ago by Vaguery

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

29 days ago by Vaguery

I like continued fractions for their elegance, their finite closure under a wider set of operations than decimal expansion, and their most-significant-part-first arithmetic. But they run for unpredictable and possibly non-terminating time before providing any information at all.

I propose that a useful real-number representation would be equivalent to intervals that could be narrowed by applying a computation. Continued fractions are such a narrowing interval: truncating at an odd number of values gives a lower bound, while truncating at an even number gives an upper bound. The problem is that not every answer gives such a narrowing interval because not all continued fractions continue. [1; 2, 2, …] is a narrowing interval, but [2], it’s square, must appear in an all-or-nothing way.

All of which begs the question, what representation should be used? It clearly will not be canonical, since we want to be able to represent two as both an finite integer and an infinitely-narrowing interval converging on two. Beyond that, it isn’t clear. Something to think about.

continued-fractions
algorithms
arithmetic
to-write-about
nudge-targets
consider:looking-to-see
I propose that a useful real-number representation would be equivalent to intervals that could be narrowed by applying a computation. Continued fractions are such a narrowing interval: truncating at an odd number of values gives a lower bound, while truncating at an even number gives an upper bound. The problem is that not every answer gives such a narrowing interval because not all continued fractions continue. [1; 2, 2, …] is a narrowing interval, but [2], it’s square, must appear in an all-or-nothing way.

All of which begs the question, what representation should be used? It clearly will not be canonical, since we want to be able to represent two as both an finite integer and an infinitely-narrowing interval converging on two. Beyond that, it isn’t clear. Something to think about.

29 days ago by Vaguery

Arithmetic with Continued Fractions

29 days ago by Vaguery

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.

continued-fractions
arithmetic
nudge-targets
consider:looking-to-see
to-write-about
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

6 weeks ago by Vaguery

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
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.

6 weeks ago by Vaguery

[1703.07856] Testing for the Equality of two Distributions on High Dimensional Object Spaces

7 weeks ago by Vaguery

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

9 weeks ago by Vaguery

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
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.

9 weeks ago by Vaguery

[1706.01557] The minimum Manhattan distance and minimum jump of permutations

9 weeks ago by Vaguery

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
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.

9 weeks ago by Vaguery

[1610.06934] The K Shortest Paths Problem with Application to Routing

9 weeks ago by Vaguery

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

9 weeks ago by Vaguery

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

9 weeks ago by Vaguery

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

9 weeks ago by Vaguery

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

10 weeks ago by Vaguery

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

10 weeks ago by Vaguery

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

**related tags**

Copy this bookmark: