Source author record

Santanu Bhowmick

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

ResearcherUnclaimed source record

Computational Geometry Computational Complexity Discrete Mathematics Other Computer Science

Catalog footprint

What is connected

4works

4topics

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.

preprint2015arXiv

A Constant Factor Approximation for Orthogonal Order Preserving Layout Adjustment

Given an initial placement of a set of rectangles in the plane, we consider the problem of finding a disjoint placement of the rectangles that minimizes the area of the bounding box and preserves the orthogonal order i.e.\ maintains the sorted ordering of the rectangle centers along both $x$-axis and $y$-axis with respect to the initial placement. This problem is known as Layout Adjustment for Disjoint Rectangles(LADR). It was known that LADR is $\mathbb{NP}$-hard, but only heuristics were known for it. We show that a certain decision version of LADR is $\mathbb{APX}$-hard, and give a constant factor approximation for LADR.

preprint2014arXiv

A Constant-Factor Approximation for Multi-Covering with Disks

We consider variants of the following multi-covering problem with disks. We are given two point sets $Y$ (servers) and $X$ (clients) in the plane, a coverage function $κ:X \rightarrow \mathcal{N}$, and a constant $α\geq 1$. Centered at each server is a single disk whose radius we are free to set. The requirement is that each client $x \in X$ be covered by at least $κ(x)$ of the server disks. The objective function we wish to minimize is the sum of the $α$-th powers of the disk radii. We present a polynomial time algorithm for this problem achieving an $O(1)$ approximation.

preprint2014arXiv

Approximation Schemes for Partitioning: Convex Decomposition and Surface Approximation

We revisit two NP-hard geometric partitioning problems - convex decomposition and surface approximation. Building on recent developments in geometric separators, we present quasi-polynomial time algorithms for these problems with improved approximation guarantees.

preprint2011arXiv

Generation of Test Vectors for Sequential Cell Verification

For Application Specific Integrated Circuits (ASIC) and System-on-Chip (SOC) designs, Cell - Based Design (CBD) is the most prevalent practice as it guarantees a shorter design cycle, minimizes errors and is easier to maintain. In modern ASIC design, standard cell methodology is practiced with sizable libraries of cells, each containing multiple implementations of the same logic functionality, in order to give the designer differing options based on area, speed or power consumption. For such library cells, thorough verification of functionality and timing is crucial for the overall success of the chip, as even a small error can prove fatal due to the repeated use of the cell in the design. Both formal and simulation based methods are being used in the industry for cell verification. We propose a method using the latter approach that generates an optimized set of test vectors for verification of sequential cells, which are guaranteed to give complete Single Input Change transition coverage with minimal redundancy. Knowledge of the cell functionality by means of the State Table is the only prerequisite of this procedure.