Source author record

Naveen Garg

Naveen Garg 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 Human-Computer Interaction Networking and Internet Architecture

Catalog footprint

What is connected

6works

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.

preprint2020arXiv

Dual Half-integrality for Uncrossable Cut Cover and its Application to Maximum Half-Integral Flow

Given an edge weighted graph and a forest $F$, the $\textit{2-edge connectivity augmentation problem}$ is to pick a minimum weighted set of edges, $E'$, such that every connected component of $E'\cup F$ is 2-edge connected. Williamson et al. gave a 2-approximation algorithm (WGMV) for this problem using the primal-dual schema. We show that when edge weights are integral, the WGMV procedure can be modified to obtain a half-integral dual. The 2-edge connectivity augmentation problem has an interesting connection to routing flow in graphs where the union of supply and demand is planar. The half-integrality of the dual leads to a tight 2-approximate max-half-integral-flow min-multicut theorem.

preprint2020arXiv

Integer Plane Multiflow Maximisation : Flow-Cut Gap and One-Quarter-Approximation

In this paper, we bound the integrality gap and the approximation ratio for maximum plane multiflow problems and deduce bounds on the flow-cut-gap. Planarity means here that the union of the supply and demand graph is planar. We first prove that there exists a multiflow of value at least half of the capacity of a minimum multicut. We then show how to convert any multiflow into a half-integer one of value at least half of the original multiflow. Finally, we round any half-integer multiflow into an integer multiflow, losing again at most half of the value, in polynomial time, achieving a $1/4$-approximation algorithm for maximum integer multiflows in the plane, and an integer-flow-cut gap of $8$.

preprint2016arXiv

A Human Computer Interaction Solution for Radiology Reporting: Evaluation of the Factors of Variation

The purpose of this research is to evaluate the human and technical factors required to create a human-computer interface (HCI) for a structured reporting solution based on eye-gaze and speech signals. Gaze and speech signals from radiologists acquired during simulated image interpretation and dictation sessions were analyzed to determine a) variation of temporal relationship between eye gaze and speech in a dictation environment, and b) variation in eye movements for a particular image interpretation task among radiologists. Knowledge of these factors provides information regarding the complexity of the image interpretation or dictation task, and provides information that can be used to design a HCI for use in diagnostic radiology. Our ultimate goal is to use these data to create an HCI to automate the generation of a particular type of structured radiology report. Our data indicate that the a) temporal relationships between eye gaze and speech and b) scan paths substantially vary among radiologists, thus implying that an HCI system based on eye gaze and speech for automating the capture of data for structured reporting processes should be customized for each user. The image resolution and layout, image content, and order of targets during an image interpretation session are not relevant factors to consider when designing an HCI. Our findings can be applied to the design of other HCI solutions for radiological applications that involve visual inspection and verbal descriptions of image findings.

preprint2014arXiv

Rejecting Jobs to Minimize Load and Maximum Flow-time

Online algorithms are usually analyzed using the notion of competitive ratio which compares the solution obtained by the algorithm to that obtained by an online adversary for the worst possible input sequence. Often this measure turns out to be too pessimistic, and one popular approach especially for scheduling problems has been that of "resource augmentation" which was first proposed by Kalyanasundaram and Pruhs. Although resource augmentation has been very successful in dealing with a variety of objective functions, there are problems for which even a (arbitrary) constant speedup cannot lead to a constant competitive algorithm. In this paper we propose a "rejection model" which requires no resource augmentation but which permits the online algorithm to not serve an epsilon-fraction of the requests. The problems considered in this paper are in the restricted assignment setting where each job can be assigned only to a subset of machines. For the load balancing problem where the objective is to minimize the maximum load on any machine, we give $O(\log^2 1/\eps)$-competitive algorithm which rejects at most an $\eps$-fraction of the jobs. For the problem of minimizing the maximum weighted flow-time, we give an $O(1/\eps^4)$-competitive algorithm which can reject at most an $\eps$-fraction of the jobs by weight. We also extend this result to a more general setting where the weights of a job for measuring its weighted flow-time and its contribution towards total allowed rejection weight are different. This is useful, for instance, when we consider the objective of minimizing the maximum stretch. We obtain an $O(1/\eps^6)$-competitive algorithm in this case. Our algorithms are immediate dispatch, though they may not be immediate reject. All these problems have very strong lower bounds in the speed augmentation model.

preprint2011arXiv

A 4/3-approximation for TSP on cubic 3-edge-connected graphs

We provide a polynomial time 4/3 approximation algorithm for TSP on metrics arising from the metric completion of cubic 3-edge connected graphs.

preprint2002arXiv

On-Line End-to-End Congestion Control

Congestion control in the current Internet is accomplished mainly by TCP/IP. To understand the macroscopic network behavior that results from TCP/IP and similar end-to-end protocols, one main analytic technique is to show that the the protocol maximizes some global objective function of the network traffic. Here we analyze a particular end-to-end, MIMD (multiplicative-increase, multiplicative-decrease) protocol. We show that if all users of the network use the protocol, and all connections last for at least logarithmically many rounds, then the total weighted throughput (value of all packets received) is near the maximum possible. Our analysis includes round-trip-times, and (in contrast to most previous analyses) gives explicit convergence rates, allows connections to start and stop, and allows capacities to change.