Given a set of points P and axisaligned rectangles R in the plane, a point p ∈ P is called exposed if it lies outside all rectangles in R. In the maxexposure problem, given an integer parameter k, we want to delete k rectangles from R so as to maximize the number of exposed points. We show that the problem is NPhard and assuming plausible complexity conjectures is also hard to approximate even when rectangles in R are translates of two fixed rectangles. However, if R only consists of translates of a single rectangle, we present a polynomialtime approximation scheme. For general rectangle range space, we present a simple O(k) bicriteria approximation algorithm; that is by deleting O(k2) rectangles, we can expose at least Ω(1/k) of the optimal number of points.
The Replenishment Schedule to Minimize Peak Storage Problem: The Gap Between the Continuous and Discrete Versions of the Problem
The replenishment storage problem (RSP) is to minimize the storage capacity requirement for a deterministic demand, multiitem inventory system, where each item has a given reorder size and cycle length. We consider the discrete RSP, where reorders can only take place at an integer time unit within the cycle. Discrete RSP was shown to be NPhard for constant joint cycle length (the least common multiple of the length of all individual cycles). We show here that discrete RSP is weakly NPhard for constant joint cycle length and prove that it is strongly NPhard for nonconstant joint cycle length. For constant joint cyclelength discrete RSP, we further present a pseudopolynomial time algorithm that solves the problem optimally and the first known fully polynomial time approximation scheme (FPTAS) for the singlecycle RSP. The scheme is utilizing a new integer programming formulation of the problem that is introduced here. For the strongly NPhard RSP with nonconstant joint cycle length, we provide a polynomial time approximation scheme (PTAS), which for any fixed [Formula: see text], provides a linear time [Formula: see text] approximate solution. The continuous RSP, where reorders can take place at any time within a cycle, seems (with our results) to be more »
 Award ID(s):
 1760102
 Publication Date:
 NSFPAR ID:
 10357236
 Journal Name:
 Operations Research
 Volume:
 67
 Issue:
 5
 Page Range or eLocationID:
 1345 to 1361
 ISSN:
 0030364X
 Sponsoring Org:
 National Science Foundation
More Like this


Establishing the complexity of {\em Bounded Distance Decoding} for ReedSolomon codes is a fundamental open problem in coding theory, explicitly asked by Guruswami and Vardy (IEEE Trans. Inf. Theory, 2005). The problem is motivated by the large current gap between the regime when it is NPhard, and the regime when it is efficiently solvable (i.e., the Johnson radius). We show the first NPhardness results for asymptotically smaller decoding radii than the maximum likelihood decoding radius of Guruswami and Vardy. Specifically, for ReedSolomon codes of length $N$ and dimension $K=O(N)$, we show that it is NPhard to decode more than $ NK c\frac{\log N}{\log\log N}$ errors (with $c>0$ an absolute constant). Moreover, we show that the problem is NPhard under quasipolynomialtime reductions for an error amount $> NK c\log{N}$ (with $c>0$ an absolute constant). An alternative natural reformulation of the Bounded Distance Decoding problem for ReedSolomon codes is as a {\em Polynomial Reconstruction} problem. In this view, our results show that it is NPhard to decide whether there exists a degree $K$ polynomial passing through $K+ c\frac{\log N}{\log\log N}$ points from a given set of points $(a_1, b_1), (a_2, b_2)\ldots, (a_N, b_N)$. Furthermore, it is NPhard under quasipolynomialtime reductions to decidemore »

In the Maximum Independent Set problem we are asked to find a set of pairwise nonadjacent vertices in a given graph with the maximum possible cardinality. In general graphs, this classical problem is known to be NPhard and hard to approximate within a factor of n1−ε for any ε > 0. Due to this, investigating the complexity of Maximum Independent Set in various graph classes in hope of finding better tractability results is an active research direction. In Hfree graphs, that is, graphs not containing a fixed graph H as an induced subgraph, the problem is known to remain NPhard and APXhard whenever H contains a cycle, a vertex of degree at least four, or two vertices of degree at least three in one connected component. For the remaining cases, where every component of H is a path or a subdivided claw, the complexity of Maximum Independent Set remains widely open, with only a handful of polynomialtime solvability results for small graphs H such as P5, P6, the claw, or the fork. We prove that for every such “possibly tractable” graph H there exists an algorithm that, given an Hfree graph G and an accuracy parameter ε > 0, findsmore »

The emergence of the InternetofThings (IoT) has inspired numerous new applications. However, due to the limited resources in current IoT infrastructures and the stringent qualityofservice requirements of the applications, providing computing and communication supports for the applications is becoming increasingly difficult. In this paper, we consider IoT applications that receive continuous data streams from multiple sources in the network, and study joint application placement and data routing to support all data streams with both bandwidth and delay guarantees. We formulate the application provisioning problem both for a single application and for multiple applications, with both cases proved to be NPhard. For the case with a single application, we propose a fully polynomialtime approximation scheme. For the multiapplication scenario, if the applications can be parallelized among multiple distributed instances, we propose a fully polynomialtime approximation scheme; for general nonparallelizable applications, we propose a randomized algorithm and analyze its performance. Simulations show that the proposed algorithms greatly improve the qualityofservice of the IoT applications compared to the heuristics.

We study robust convex quadratic programs where the uncertain problem parameters can contain both continuous and integer components. Under the natural boundedness assumption on the uncertainty set, we show that the generic problems are amenable to exact copositive programming reformulations of polynomial size. These convex optimization problems are NPhard but admit a conservative semidefinite programming (SDP) approximation that can be solved efficiently. We prove that the popular approximate Slemma method—which is valid only in the case of continuous uncertainty—is weaker than our approximation. We also show that all results can be extended to the twostage robust quadratic optimization setting if the problem has complete recourse. We assess the effectiveness of our proposed SDP reformulations and demonstrate their superiority over the stateoftheart solution schemes on instances of least squares, project management, and multiitem newsvendor problems.