- arXiv.org
- Applied Physics
- Popular Physics
- History and Philosophy of Physics
- Optics
- Fluid Dynamics
- Physics and Society
- Biological Physics
- Space Physics
- General Physics
- Data Analysis, Statistics and Probability
- Atomic Physics
- Geophysics
- Atomic and Molecular Clusters
- Medical Physics
- Plasma Physics
- Instrumentation and Detectors
- Physics Education
- Atmospheric and Oceanic Physics
- Chemical Physics
- Computational Physics
- Classical Physics
- Accelerator Physics

- Number Theory
- Statistics Theory
- History and Overview
- Information Theory
- Analysis of PDEs
- Algebraic Geometry
- Combinatorics
- Symplectic Geometry
- Mathematical Physics
- Complex Variables
- Probability
- Operator Algebras
- Group Theory
- Representation Theory
- Quantum Algebra
- Numerical Analysis
- Geometric Topology
- Dynamical Systems
- Differential Geometry
- Logic
- Optimization and Control
- General Topology
- General Mathematics
- Metric Geometry
- Algebraic Topology
- Functional Analysis
- Classical Analysis and ODEs
- Spectral Theory
- Category Theory
- Commutative Algebra
- Rings and Algebras
- K-Theory and Homology

- General Literature
- Neural and Evolutionary Computing
- Symbolic Computation
- Information Theory
- Mathematical Software
- Emerging Technologies
- Computer Vision and Pattern Recognition
- Learning
- Operating Systems
- Programming Languages
- Software Engineering
- Multiagent Systems
- Social and Information Networks
- Sound
- Information Retrieval
- Databases
- Formal Languages and Automata Theory
- Distributed, Parallel, and Cluster Computing
- Computer Science and Game Theory
- Artificial Intelligence
- Cryptography and Security
- Computational Complexity
- Discrete Mathematics
- Hardware Architecture
- Numerical Analysis
- Human-Computer Interaction
- Other Computer Science
- Systems and Control
- Digital Libraries
- Robotics
- Networking and Internet Architecture
- Logic in Computer Science
- Computational Geometry
- Data Structures and Algorithms
- Computational Engineering, Finance, and Science
- Graphics
- Performance
- Computation and Language
- Multimedia
- Computers and Society

- Symmetry in mathematical programming may lead to a multiplicity of solutions. In nonconvex optimisation, it can negatively affect the performance of the Branch and Bound algorithm. Symmetry may induce large search trees with multiple equivalent solutions, i.e. with the same optimal value. Dealing with symmetry requires detecting and classifying it first. This paper develops several methods for detecting symmetry in quadratically constrained quadratic optimisation problems via adjacency matrices. Using graph theory, we transform these matrices into binary layered graphs and enter them into the software package nauty. Nauty generates important symmetric properties of the original problem.
- Dec 15 2017 cs.DS arXiv:1712.05218v1We introduce and study a class of optimization problems we coin replenishment problems with fixed turnover times: a very natural model that has received little attention in the literature. Nodes with capacity for storing a certain commodity are located at various places; at each node the commodity depletes within a certain time, the turnover time, which is constant but can vary between locations. Nodes should never run empty, and to prevent this we may schedule nodes for replenishment every day. The natural feature that makes this problem interesting is that we may schedule a replenishment (well) before a node becomes empty, but then the next replenishment will be due earlier also. This added workload needs to be balanced against the cost of routing vehicles to do the replenishments. In this paper, we focus on the aspect of minimizing routing costs. However, the framework of recurring tasks, in which the next job of a task must be done within a fixed amount of time after the previous one is much more general and gives an adequate model for many practical situations. Note that our problem has an infinite time horizon. However, it can be fully characterized by a compact input, containing only the location of each store and a turnover time. This makes determining its computational complexity highly challenging and indeed it remains essentially unresolved. We study the problem for two objectives: min-avg minimizes the average tour length and min-max minimizes the maximum tour length over all days. For min-max we derive a logarithmic factor approximation for the problem on general metrics and a 6-approximation for the problem on trees, for which we have a proof of NP-hardness. For min-avg we present a logarithmic approximation on general metrics, 2-approximation for trees, and a pseudopolynomial time algorithm for the line. Many intriguing problems remain open.
- B-slack trees, a subclass of B-trees that have substantially better worst-case space complexity, are introduced. They store $n$ keys in height $O(\log_b n)$, where $b$ is the maximum node degree. Updates can be performed in $O(\log_{\frac b 2} n)$ amortized time. A relaxed balance version, which is well suited for concurrent implementation, is also presented.
- A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for \textscMaximum Clique on unit disk graphs [Clark, Colbourn, Johnson; Discrete Mathematics '90]. Since then, it has been an intriguing open question whether or not tractability can be extended to general disk graphs. We show the rather surprising structural result that a disjoint union of cycles is the complement of a disk graph if and only if at most one of those cycles is of odd length. From that, we derive the first QPTAS and subexponential algorithm running in time $2^{\tilde{O}(n^{2/3})}$ for \textscMaximum Clique on disk graphs. In stark contrast, \textscMaximum Clique on intersection graph of filled ellipses or filled triangles is unlikely to have such algorithms, even when the ellipses are close to unit disks. Indeed, we show that there is a constant approximation which is not attainable even in time $2^{n^{1-\varepsilon}}$, unless the Exponential Time Hypothesis fails.

LCL problems on grids

Māris Ozols Feb 21 2017 15:35 UTCZoltán Zimborás Jan 12 2017 20:38 UTC

Here is a nice description, with additional links, about the importance of this work if it turns out to be flawless (thanks a lot to Martin Schwarz for this link): [dichotomy conjecture][1].

[1]: http://processalgebra.blogspot.com/2017/01/has-feder-vardi-dichotomy-conjecture.html

Māris Ozols Oct 21 2016 21:06 UTC

...(continued)Very nice! Now we finally know how to fairly cut a cake in a finite number of steps! What is more, the number of steps is expected to go down from the whopping $n^{n^{n^{n^{n^n}}}}$ to just barely $n^{n^n}$. I can't wait to get my slice!

https://www.quantamagazine.org/20161006-new-algorithm-solve

Ashley Apr 21 2015 18:42 UTC

...(continued)Thanks for the further comments and spotting the new typos. To reply straight away to the other points:

First, the resulting states might as well stay in the same bin (even though, as you rightly note, the bins no longer correspond to the same bit-strings as before). All that matters is that the

Perplexed Platypus Apr 21 2015 14:55 UTC

...(continued)Thanks for updating the paper so promptly. The updated version addresses all my concerns so far. However I noticed a few extra (minor) things while reading through it.

On page 15, last step of 2(b): if $|\psi_r\rangle$ and $|\psi_t\rangle$ were in the same bin but the combination operation failed

Ashley Apr 20 2015 16:27 UTC

...(continued)Thank you for these very detailed and helpful comments. I have uploaded a new version of the paper to the arXiv to address them, which should appear tomorrow. I will reply to the comments in more detail (and justify the cases where I didn't modify the paper as suggested) when I receive them through

Perplexed Platypus Apr 13 2015 22:37 UTC

...(continued)**Summary and recommendation**

This paper considers a $d$-dimensional version of the problem of finding a given pattern within a text, for random patterns and text. The text is assumed to be picked uniformly at random and has size $n^d$ while the pattern has size $m^d$ and is either uniformly ran

Ashley Apr 12 2015 13:01 UTC

Thanks for the clarification. In fact it seems that I do have this option switched on, with the correct author identifier, so I'm not sure why I didn't get an email about these comments.

Perplexed Platypus Apr 10 2015 13:18 UTC

...(continued)Hi Ashley,

Thanks for your reply, it was very helpful! I thought about e-mailing you but I wanted to preserve my confidentiality as a reviewer. Also, I wanted to see if it is feasible to use SciRate as a platform for interacting with authors during the review process.

I encourage you (and **ot

Ashley Apr 09 2015 20:03 UTC

...(continued)Hi,

Thank you for your very detailed comments / questions about the technical points in this paper. I did happen to check Scirate today but in general (as I suspect with many other people) I don't check it regularly, so for reliable replies it's better just to email me. To reply to your questions i

- Supported by Silverpond.