Zobrazeno 1 - 10
of 22
pro vyhledávání: '"Nitish Korula"'
Publikováno v:
Management Science.
Buying display ad impressions via real-time auctions comes with significant allocation and price uncertainties. We design and analyze a contract that mitigates this uncertainty risk by providing guaranteed allocation and prices while maintaining the
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::1817687cfb7702de0b25ac04ff6a585e
https://doi.org/10.1287/mnsc.2022.4542
https://doi.org/10.1287/mnsc.2022.4542
Publikováno v:
SSRN Electronic Journal.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::dab3228fb576caecac2b38b92409f7cc
https://doi.org/10.2139/ssrn.3088600
https://doi.org/10.2139/ssrn.3088600
Publikováno v:
STOC
In the Submodular Welfare Maximization (SWM) problem, the input consists of a set of n items, each of which must be allocated to one of m agents. Each agent l has a valuation function vl, where vl(S) denotes the welfare obtained by this agent if she
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d70d4bdf5a482425330c2467a14d3601
Publikováno v:
Algorithmica. 72:493-514
In the {\em capacitated} survivable network design problem (Cap-SNDP), we are given an undirected multi-graph where each edge has a capacity and a cost. The goal is to find a minimum cost subset of edges that satisfies a given set of pairwise minimum
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::29e7ac55c4c04a0310a5767fa7205f80
https://doi.org/10.1007/s00453-013-9862-4
https://doi.org/10.1007/s00453-013-9862-4
Autor:
Nitish Korula, Chandra Chekuri
Publikováno v:
SIAM Journal on Discrete Mathematics. 28:577-597
Given an undirected graph $G=(V,E)$ and a subset of vertices called terminals $T \subseteq V$, the element-connectivity $\elconn_G(u,v)$ of two terminals $u,v \in T$ is the maximum number of $u$-$v$ paths that are pairwise element-disjoint, that is,
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::70bde92294cb42a7b888e833a084cda3
https://doi.org/10.1137/120882147
https://doi.org/10.1137/120882147
Publikováno v:
WWW
Linking accounts of the same user across datasets -- even when personally identifying information is removed or unavailable -- is an important open problem studied in many contexts. Beyond many practical applications, (such as cross domain analysis,
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e03e51a9eaf9cd50d28cdd27bcd79201
https://doi.org/10.1145/2872427.2883002
https://doi.org/10.1145/2872427.2883002
Publikováno v:
ACM Transactions on Algorithms. 8:1-27
In this article, we consider the orienteering problem in undirected and directed graphs and obtain improved approximation algorithms. The point to point-orienteering problem is the following: Given an edge-weighted graph G =( V, E ) (directed or undi
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ade3ed7fd57fc4f5f55abf075547330f
https://doi.org/10.1145/2229163.2229167
https://doi.org/10.1145/2229163.2229167
Publikováno v:
Theory of Computing. 8:533-565
We give new approximation algorithms for packing integer programs (PIPs) by employing the method of randomized rounding combined with alterations. Our first result is a simpler approximation algorithm for general PIPs which matches the best known bou
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::559cec6c2b766d67ac9092b330241cbb
https://doi.org/10.4086/toc.2012.v008a024
https://doi.org/10.4086/toc.2012.v008a024
Autor:
Timothy D. LeSaulnier, Daniel W. Cranston, Jennifer Vandenbussche, Kevin G. Milans, Douglas B. West, Christopher J. Stocker, Nitish Korula
Publikováno v:
Journal of Graph Theory. 70:10-28
An overlap representation of a graph G assigns sets to vertices so that vertices are adjacent if and only if their assigned sets intersect with neither containing the other. The overlap number φ(G) (introduced by Rosgen) is the minimum size of the u
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::5097ea3182270ed77a2eb939cb1d65e9
https://doi.org/10.1002/jgt.20596
https://doi.org/10.1002/jgt.20596
Autor:
Chandra Chekuri, Nitish Korula
Publikováno v:
Algorithmica. 62:436-463
Given an edge-weighted undirected graph $G$ with a specified set of terminals, let the \emph{density} of any subgraph be the ratio of its weight/cost to the number of terminals it contains. If $G$ is 2-connected, does it contain smaller 2-connected s
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d9a8a079bb8901eb133513f5b85e7942
https://doi.org/10.1007/s00453-010-9462-5
https://doi.org/10.1007/s00453-010-9462-5