Source author record

Rebecca Hoberg

Rebecca Hoberg appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity Computational Geometry Discrete Mathematics math.CO math.GT math.OC

Catalog footprint

What is connected

4works

7topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2016arXiv

An Improved Deterministic Rescaling for Linear Programming Algorithms

The perceptron algorithm for linear programming, arising from machine learning, has been around since the 1950s. While not a polynomial-time algorithm, it is useful in practice due to its simplicity and robustness. In 2004, Dunagan and Vempala showed that a randomized rescaling turns the perceptron method into a polynomial time algorithm, and later Peña and Soheili gave a deterministic rescaling. In this paper, we give a deterministic rescaling for the perceptron algorithm that improves upon the previous rescaling methods by making it possible to rescale much earlier. This results in a faster running time for the rescaled perceptron algorithm. We will also demonstrate that the same rescaling methods yield a polynomial time algorithm based on the multiplicative weights update method. This draws a connection to an area that has received a lot of recent attention in theoretical computer science.

preprint2016arXiv

Number Balancing is as hard as Minkowski's Theorem and Shortest Vector

The number balancing (NBP) problem is the following: given real numbers $a_1,\ldots,a_n \in [0,1]$, find two disjoint subsets $I_1,I_2 \subseteq [n]$ so that the difference $|\sum_{i \in I_1}a_i - \sum_{i \in I_2}a_i|$ of their sums is minimized. An application of the pigeonhole principle shows that there is always a solution where the difference is at most $O(\frac{\sqrt{n}}{2^n})$. Finding the minimum, however, is NP-hard. In polynomial time,the differencing algorithm by Karmarkar and Karp from 1982 can produce a solution with difference at most $n^{-Θ(\log n)}$, but no further improvement has been made since then. In this paper, we show a relationship between NBP and Minkowski's Theorem. First we show that an approximate oracle for Minkowski's Theorem gives an approximate NBP oracle. Perhaps more surprisingly, we show that an approximate NBP oracle gives an approximate Minkowski oracle. In particular, we prove that any polynomial time algorithm that guarantees a solution of difference at most $2^{\sqrt{n}} / 2^{n}$ would give a polynomial approximation for Minkowski as well as a polynomial factor approximation algorithm for the Shortest Vector Problem.

preprint2015arXiv

A Logarithmic Additive Integrality Gap for Bin Packing

For bin packing, the input consists of $n$ items with sizes $s_1,...,s_n \in [0,1]$ which have to be assigned to a minimum number of bins of size 1. Recently, the second author gave an LP-based polynomial time algorithm that employed techniques from discrepancy theory to find a solution using at most $OPT + O(\log OPT \cdot \log \log OPT)$ bins. In this paper, we present an approximation algorithm that has an additive gap of only $O(\log OPT)$ bins, which matches certain combinatorial lower bounds. Any further improvement would have to use more algebraic structure. Our improvement is based on a combination of discrepancy theory techniques and a novel 2-stage packing: first we pack items into containers; then we pack containers into bins of size 1. Apart from being more effective, we believe our algorithm is much cleaner than the one of Rothvoss.

preprint2012arXiv

The Theory of Pseudoknots

Classical knots in $\mathbb{R}^3$ can be represented by diagrams in the plane. These diagrams are formed by curves with a finite number of transverse crossings, where each crossing is decorated to indicate which strand of the knot passes over at that point. A pseudodiagram is a knot diagram that may be missing crossing information at some of its crossings. At these crossings, it is undetermined which strand passes over. Pseudodiagrams were first introduced by Ryo Hanaki in 2010. Here, we introduce the notion of a pseudoknot, i.e. an equivalence class of pseudodiagrams under an appropriate choice of Reidemeister moves. In order to begin a classification of pseudoknots, we introduce the concept of a weighted resolution set, an invariant of pseudoknots. We compute the weighted resolution set for several pseudoknot families and discuss notions of crossing number, homotopy, and chirality for pseudoknots.