BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Kevin Zemmer

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

ResearcherUnclaimed source record
math.OC

Catalog footprint

What is connected

2works
1topics
3close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

2 published item(s)

preprint2015arXiv

An FPTAS for Minimizing Indefinite Quadratic Forms over Integers in Polyhedra

We present a generic approach that allows us to develop a fully polynomial-time approximation scheme (FTPAS) for minimizing nonlinear functions over the integer points in a rational polyhedron in fixed dimension. The approach combines the subdivision strategy of Papadimitriou and Yannakakis (2000) with ideas similar to those commonly used to derive real algebraic certificates of positivity for polynomials. Our general approach is widely applicable. We apply it, for instance, to the Motzkin polynomial and to indefinite quadratic forms $x^T Q x$ in a fixed number of variables, where $Q$ has at most one positive, or at most one negative eigenvalue. In dimension three, this leads to an FPTAS for general $Q$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Minimizing Cubic and Homogeneous Polynomials over Integers in the Plane

We complete the complexity classification by degree of minimizing a polynomial over the integer points in a polyhedron in $\mathbb{R}^2$. Previous work shows that optimizing a quadratic polynomial over the integer points in a polyhedral region in $\mathbb{R}^2$ can be done in polynomial time, while optimizing a quartic polynomial in the same type of region is NP-hard. We close the gap by showing that this problem can be solved in polynomial time for cubic polynomials. Furthermore, we show that the problem of minimizing a homogeneous polynomial of any fixed degree over the integer points in a bounded polyhedron in $\mathbb{R}^2$ is solvable in polynomial time. We show that this holds for polynomials that can be translated into homogeneous polynomials, even when the translation vector is unknown. We demonstrate that such problems in the unbounded case can have smallest optimal solutions of exponential size in the size of the input, thus requiring a compact representation of solutions for a general polynomial time algorithm for the unbounded case.

0 citations0 reviewsNo code linkedOpen access