LIVIVO - Search results -

Search results

Result 1 - 10 of total 10

Search options

Book ; Online: An Approximation Algorithm for Covering Linear Programs and its Application to Bin-Packing

Sharma, Eklavya

2020

Abstract: We give an $\alpha(1+\epsilon)$-approximation algorithm for solving covering LPs, assuming the presence of a $(1/\alpha)$-approximation algorithm for a certain optimization problem. Our algorithm is based on a simple modification of the Plotkin-Shmoys- ... ...

Abstract	We give an $\alpha(1+\epsilon)$-approximation algorithm for solving covering LPs, assuming the presence of a $(1/\alpha)$-approximation algorithm for a certain optimization problem. Our algorithm is based on a simple modification of the Plotkin-Shmoys-Tardos algorithm (MOR 1995). We then apply our algorithm to $\alpha(1+\epsilon)$-approximately solve the configuration LP for a large class of bin-packing problems, assuming the presence of a $(1/\alpha)$-approximate algorithm for the corresponding knapsack problem (KS). Previous results give us a PTAS for the configuration LP using a PTAS for KS. Those results don't extend to the case where KS is poorly approximated. Our algorithm, however, works even for polynomially-large $\alpha$. Comment: Update: added acknowledgements
Keywords	Computer Science - Data Structures and Algorithms
Publishing date	2020-11-23
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Analysis of the Harmonic Function Used in Bin-Packing

Sharma, Eklavya

2020

Abstract: The harmonic function was first introduced by Lee and Lee (JACM 1985) for analyzing their online bin-packing algorithm. Subsequently, it has been used to obtain approximation algorithms for many different packing problems. Here we slightly generalize the ...

Abstract	The harmonic function was first introduced by Lee and Lee (JACM 1985) for analyzing their online bin-packing algorithm. Subsequently, it has been used to obtain approximation algorithms for many different packing problems. Here we slightly generalize the harmonic function and give alternative proofs of its important properties. Comment: Update: fixed typo and added acknowledgements
Keywords	Computer Science - Data Structures and Algorithms ; Computer Science - Discrete Mathematics
Publishing date	2020-11-23
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Harmonic Algorithms for Packing d-dimensional Cuboids Into Bins

Sharma, Eklavya

2020

Abstract: We explore approximation algorithms for the $d$-dimensional geometric bin packing problem ($d$BP). Caprara (MOR 2008) gave a harmonic-based algorithm for $d$BP having an asymptotic approximation ratio (AAR) of $T_{\infty}^{d-1}$ (where $T_{\infty} \ ... ...

Abstract	We explore approximation algorithms for the $d$-dimensional geometric bin packing problem ($d$BP). Caprara (MOR 2008) gave a harmonic-based algorithm for $d$BP having an asymptotic approximation ratio (AAR) of $T_{\infty}^{d-1}$ (where $T_{\infty} \approx 1.691$). However, their algorithm doesn't allow items to be rotated. This is in contrast to some common applications of $d$BP, like packing boxes into shipping containers. We give approximation algorithms for $d$BP when items can be orthogonally rotated about all or a subset of axes. We first give a fast and simple harmonic-based algorithm having AAR $T_{\infty}^{d}$. We next give a more sophisticated harmonic-based algorithm, which we call $\mathtt{HGaP}_k$, having AAR $T_{\infty}^{d-1}(1+\epsilon)$. This gives an AAR of roughly $2.860 + \epsilon$ for 3BP with rotations, which improves upon the best-known AAR of $4.5$. In addition, we study the multiple-choice bin packing problem that generalizes the rotational case. Here we are given $n$ sets of $d$-dimensional cuboidal items and we have to choose exactly one item from each set and then pack the chosen items. Our algorithms also work for the multiple-choice bin packing problem. We also give fast and simple approximation algorithms for the multiple-choice versions of $d$D strip packing and $d$D geometric knapsack. Comment: Update 3: slightly improve readability, mention dependence on d; Update 2: major refactoring; Update 1: fix typos, slightly improve readability, use title-case for title
Keywords	Computer Science - Computational Geometry ; Computer Science - Data Structures and Algorithms
Subject code	005
Publishing date	2020-11-22
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Nash Equilibria of Two-Player Matrix Games Repeated Until Collision

Murhekar, Aniket / Sharma, Eklavya

2023

Abstract: We introduce and initiate the study of a natural class of repeated two-player matrix games, called Repeated-Until-Collision (RUC) games. In each round, both players simultaneously pick an action from a common action set $\{1, 2, \dots, n\}$. Depending on ...

Abstract	We introduce and initiate the study of a natural class of repeated two-player matrix games, called Repeated-Until-Collision (RUC) games. In each round, both players simultaneously pick an action from a common action set $\{1, 2, \dots, n\}$. Depending on their chosen actions, they derive payoffs given by $n \times n$ matrices $A$ and $B$, respectively. If their actions collide (i.e., they pick the same action), the game ends, otherwise, it proceeds to the next round. Both players want to maximize their total payoff until the game ends. RUC games can be interpreted as pursuit-evasion games or repeated hide-and-seek games. They also generalize hand cricket, a popular game among children in India. We show that under mild assumptions on the payoff matrices, every RUC game admits a Nash equilibrium (NE). Moreover, we show the existence of a stationary NE, where each player chooses their action according to a probability distribution over the action set that does not change across rounds. Remarkably, we show that all NE are effectively the same as the stationary NE, thus showing that RUC games admit an almost unique NE. Lastly, we also show how to compute (approximate) NE for RUC games. Comment: Accepted to FSTTCS 2023
Keywords	Computer Science - Computer Science and Game Theory
Subject code	700
Publishing date	2023-09-26
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Existence and Computation of Epistemic EFX

Garg, Jugal / Sharma, Eklavya

2022

Abstract: We consider the problem of allocating indivisible goods among $n$ agents in a fair manner. For this problem, one of the best notions of fairness is envy-freeness up to any good (EFX). However, it is not known if EFX allocations always exist. Hence, ... ...

Abstract	We consider the problem of allocating indivisible goods among $n$ agents in a fair manner. For this problem, one of the best notions of fairness is envy-freeness up to any good (EFX). However, it is not known if EFX allocations always exist. Hence, several relaxations of EFX allocations have been studied. We propose another relaxation of EFX, called epistemic EFX (EEFX). An allocation is EEFX iff for every agent $i$, it is possible to shuffle the goods of the other agents such that agent $i$ does not envy any other agent up to any good. We show that EEFX allocations always exist for additive valuations, and give a polynomial-time algorithm for computing them. We also show how EEFX is related to some previously-known notions of fairness.
Keywords	Computer Science - Computer Science and Game Theory
Publishing date	2022-06-03
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Simplification and Improvement of MMS Approximation

Akrami, Hannaneh / Garg, Jugal / Sharma, Eklavya / Taki, Setareh

2023

Abstract: We consider the problem of fairly allocating a set of indivisible goods among $n$ agents with additive valuations, using the popular fairness notion of maximin share (MMS). Since MMS allocations do not always exist, a series of works provided existence ... ...

Abstract	We consider the problem of fairly allocating a set of indivisible goods among $n$ agents with additive valuations, using the popular fairness notion of maximin share (MMS). Since MMS allocations do not always exist, a series of works provided existence and algorithms for approximate MMS allocations. The current best approximation factor, for which the existence is known, is $(\frac{3}{4} + \frac{1}{12n})$ [Garg and Taki, 2021]. Most of these results are based on complicated analyses, especially those providing better than $2/3$ factor. Moreover, since no tight example is known of the Garg-Taki algorithm, it is unclear if this is the best factor of this approach. In this paper, we significantly simplify the analysis of this algorithm and also improve the existence guarantee to a factor of $(\frac{3}{4} + \min(\frac{1}{36}, \frac{3}{16n-4}))$. For small $n$, this provides a noticeable improvement. Furthermore, we present a tight example of this algorithm, showing that this may be the best factor one can hope for with the current techniques.
Keywords	Computer Science - Computer Science and Game Theory
Subject code	306
Publishing date	2023-03-29
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Tight Approximation Algorithms for Geometric Bin Packing with Skewed Items

Khan, Arindam / Sharma, Eklavya

2021

Abstract: In the Two-dimensional Bin Packing (2BP) problem, we are given a set of rectangles of height and width at most one and our goal is to find an axis-aligned nonoverlapping packing of these rectangles into the minimum number of unit square bins. The problem ...

Abstract	In the Two-dimensional Bin Packing (2BP) problem, we are given a set of rectangles of height and width at most one and our goal is to find an axis-aligned nonoverlapping packing of these rectangles into the minimum number of unit square bins. The problem admits no APTAS and the current best approximation ratio is $1.406$ by Bansal and Khan [SODA'14]. A well-studied variant of the problem is Guillotine Two-dimensional Bin Packing (G2BP), where all rectangles must be packed in such a way that every rectangle in the packing can be obtained by recursively applying a sequence of end-to-end axis-parallel cuts, also called guillotine cuts. Bansal, Lodi, and Sviridenko [FOCS'05] obtained an APTAS for this problem. Let $\lambda$ be the smallest constant such that for every set $I$ of items, the number of bins in the optimal solution to G2BP for $I$ is upper bounded by $\lambda\operatorname{opt}(I) + c$, where $\operatorname{opt}(I)$ is the number of bins in the optimal solution to 2BP for $I$ and $c$ is a constant. It is known that $4/3 \le \lambda \le 1.692$. Bansal and Khan [SODA'14] conjectured that $\lambda = 4/3$. The conjecture, if true, will imply a $(4/3+\varepsilon)$-approximation algorithm for 2BP. According to convention, for a given constant $\delta>0$, a rectangle is large if both its height and width are at least $\delta$, and otherwise it is called skewed. We make progress towards the conjecture by showing $\lambda = 4/3$ for skewed instance, i.e., when all input rectangles are skewed. Even for this case, the previous best upper bound on $\lambda$ was roughly 1.692. We also give an APTAS for 2BP for skewed instance, though general 2BP does not admit an APTAS.
Keywords	Computer Science - Computational Geometry ; Computer Science - Data Structures and Algorithms
Subject code	005
Publishing date	2021-05-06
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Approximation Algorithms for Generalized Multidimensional Knapsack

Khan, Arindam / Sharma, Eklavya / Sreenivas, K. V. N.

2021

Abstract: We study a generalization of the knapsack problem with geometric and vector constraints. The input is a set of rectangular items, each with an associated profit and $d$ nonnegative weights ($d$-dimensional vector), and a square knapsack. The goal is to ... ...

Abstract	We study a generalization of the knapsack problem with geometric and vector constraints. The input is a set of rectangular items, each with an associated profit and $d$ nonnegative weights ($d$-dimensional vector), and a square knapsack. The goal is to find a non-overlapping axis-parallel packing of a subset of items into the given knapsack such that the vector constraints are not violated, i.e., the sum of weights of all the packed items in any of the $d$ dimensions does not exceed one. We consider two variants of the problem: $(i)$ the items are not allowed to be rotated, $(ii)$ items can be rotated by 90 degrees. We give a $(2+\epsilon)$-approximation algorithm for this problem (both versions). In the process, we also study a variant of the maximum generalized assignment problem (Max-GAP), called Vector-Max-GAP, and design a PTAS for it.
Keywords	Computer Science - Data Structures and Algorithms ; Computer Science - Computational Geometry
Subject code	000
Publishing date	2021-02-11
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Article ; Online: Salivary L-fucose as a biomarker for oral potentially malignant disorders and oral cancer.

Sharma, Mudita / Sharma, Eklavya / Prabhu, Vishnudas / Pai, Vinitha Ramanath / D'souza, Jyothi Mp / Harish, Sindhu / Jose, Maji

Journal of cancer research and therapeutics

2020 Volume 16, Issue 3, Page(s) 546–550

Abstract: Background: The objective of this study was to evaluate the serum and salivary L-fucose in oral potentially malignant disorders (OPMDs) and oral cancer (OC) in order to investigate the possibility of using this as biomarker for early diagnosis.: ... ...

Abstract	Background: The objective of this study was to evaluate the serum and salivary L-fucose in oral potentially malignant disorders (OPMDs) and oral cancer (OC) in order to investigate the possibility of using this as biomarker for early diagnosis. Materials and methods: The study included 85 participants, who were grouped as control (30), OPMDs patients (25), and OC patients (30). Serum and unstimulated whole saliva were collected from participants of all groups and fucose estimation was done using spectrophotometry. The results were tabulated and analyzed statistically. Results: The mean serum L-fucose levels in normal, OPMDs, and OC group were 3.49, 19.18, and 35.75 mg/dl, respectively, while the levels of salivary L-fucose were 3.18, 7.02, and 11.66 mg/dl, respectively. A highly significant rise (P < 0.001) in serum and salivary L-fucose was observed in the study participants compared to control. Conclusions: The present study showed a significant and gradual increase in serum and salivary L-fucose from control to OPMDs to OC. From this study, we suggest that L-fucose can be used as a reliable biomarker and saliva can be used as a diagnostic fluid for screening and early detection of OC.
MeSH term(s)	Biomarkers, Tumor/blood ; Biomarkers, Tumor/metabolism ; Carcinoma, Squamous Cell/blood ; Carcinoma, Squamous Cell/pathology ; Case-Control Studies ; Female ; Fucose/blood ; Fucose/chemistry ; Fucose/metabolism ; Humans ; Male ; Mouth Neoplasms/blood ; Mouth Neoplasms/metabolism ; Mouth Neoplasms/pathology ; Precancerous Conditions/blood ; Precancerous Conditions/pathology ; Saliva/chemistry ; Saliva/metabolism
Chemical Substances	Biomarkers, Tumor ; Fucose (28RYY2IV3F)
Keywords	covid19
Language	English
Publishing date	2020-07-23
Publishing country	India
Document type	Journal Article
ZDB-ID	2187633-2
ISSN	1998-4138 ; 0973-1482
ISSN (online)	1998-4138
ISSN	0973-1482
DOI	10.4103/jcrt.JCRT_552_17
Database	MEDical Literature Analysis and Retrieval System OnLINE

Order via subito

This service is chargeable due to the Delivery terms set by subito. Orders including an article and supplementary material will be classified as separate orders. In these cases, fees will be demanded for each order.

Article: Salivary L-fucose as a biomarker for oral potentially malignant disorders and oral cancer

Sharma, Mudita / Sharma, Eklavya / Prabhu, Vishnudas / Pai, Vinitha Ramanath / D039, / souza, Jyothi Mp / Harish, Sindhu / Jose, Maji

J Cancer Res Ther

Abstract	Background: The objective of this study was to evaluate the serum and salivary L-fucose in oral potentially malignant disorders (OPMDs) and oral cancer (OC) in order to investigate the possibility of using this as biomarker for early diagnosis. Materials and Methods: The study included 85 participants, who were grouped as control (30), OPMDs patients (25), and OC patients (30). Serum and unstimulated whole saliva were collected from participants of all groups and fucose estimation was done using spectrophotometry. The results were tabulated and analyzed statistically. Results: The mean serum L-fucose levels in normal, OPMDs, and OC group were 3.49, 19.18, and 35.75 mg/dl, respectively, while the levels of salivary L-fucose were 3.18, 7.02, and 11.66 mg/dl, respectively. A highly significant rise (P < 0.001) in serum and salivary L-fucose was observed in the study participants compared to control. Conclusions: The present study showed a significant and gradual increase in serum and salivary L-fucose from control to OPMDs to OC. From this study, we suggest that L-fucose can be used as a reliable biomarker and saliva can be used as a diagnostic fluid for screening and early detection of OC.
Keywords	covid19
Publisher	WHO
Document type	Article
Note	WHO #Covidence: #32719265
Database	COVID19

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Details ▾

To top

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

More links

Kategorien

Order via subito

Kategorien

Inter-library loan at ZB MED