Zobrazeno 91 - 100
of 162
pro vyhledávání: '"PINYAN LU"'
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783642255090
WINE
WINE
In revenue maximization of selling a digital product in a social network, the utility of an agent is often considered to have two parts: a private valuation, and linearly additive influences from other agents. We study the incomplete information case
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::39059c6b670aabeb6979ee913f5f429b
https://doi.org/10.1007/978-3-642-25510-6_5
https://doi.org/10.1007/978-3-642-25510-6_5
We give the first deterministic fully polynomial-time approximation scheme (FPTAS) for computing the partition function of a two-state spin system on an arbitrary graph, when the parameters of the system satisfy the uniqueness condition on infinite r
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e6849bc3752a534ad271fcdf9fa1ce09
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783642255090
WINE
WINE
We consider the problem of designing a profit-maximizing single-item auction, where the valuations of bidders are correlated. We revisit the k-lookahead auction introduced by Ronen [6] and recently further developed by Dobzinski, Fu and Kleinberg [2]
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::7ae2bfa98438ac11608c1ed7ce8f3154
https://doi.org/10.1007/978-3-642-25510-6_6
https://doi.org/10.1007/978-3-642-25510-6_6
Publikováno v:
Automata, Languages and Programming ISBN: 9783642220050
ICALP (1)
ICALP (1)
For certain subclasses of NP, ⊕P or #P characterized by local constraints, it is known that if there exist any problems that are not polynomial time computable within that subclass, then those problems are NP-, ⊕P- or #P-complete. Such dichotomy
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::1e78a82c5b5f078ec228e52d24d1763c
https://doi.org/10.1007/978-3-642-22006-7_60
https://doi.org/10.1007/978-3-642-22006-7_60
We give a complete characterization of the two-state anti-ferromagnetic spin systems which are of strong spatial mixing on general graphs. We show that a two-state anti-ferromagnetic spin system is of strong spatial mixing on all graphs of maximum de
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1b6d009f34694728d13886b1f5637f5c
Publikováno v:
FOCS
Valiant introduced match gate computation and holographic algorithms. A number of seemingly exponential time problems can be solved by this novel algorithmic paradigm in polynomial time. We show that, in a very strong sense, match gate computations a
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ed2b64a36efa68ce978b660624f23d3e
http://arxiv.org/abs/1008.0683
http://arxiv.org/abs/1008.0683
Publikováno v:
EC
We consider the problem of locating facilities in a metric space to serve a set of selfish agents. The cost of an agent is the distance between her own location and the nearest facility. The social cost is the total cost of the agents. We are interes
Publikováno v:
Frontiers in Algorithmics ISBN: 9783642145520
We consider the problem of evaluating certain exponential sums. These sums take the form $\sum_{x_1,...,x_n \in Z_N} e^{f(x_1,...,x_n) {2 \pi i / N}} $, where each x_i is summed over a ring Z_N, and f(x_1,...,x_n) is a multivariate polynomial with in
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::2e95cafded45cdf98f99a382f7937f6b
https://doi.org/10.1007/978-3-642-14553-7_16
https://doi.org/10.1007/978-3-642-14553-7_16
Publikováno v:
Automata, Languages and Programming ISBN: 9783642141645
ICALP (1)
ICALP (1)
Graph homomorphism problem has been studied intensively. Given an m × m symmetric matrix A, the graph homomorphism function ZA(G) is defined as ZA(G) = σξ:V →[m] (u,v)∈E ΠAξ(u),ξ(v), where G = (V,E) is any undirected graph. The function ZA(
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::47304e21e9b93fc4bb3ba585b44ef8ba
https://doi.org/10.1007/978-3-642-14165-2_24
https://doi.org/10.1007/978-3-642-14165-2_24
Publikováno v:
Algorithmica
We explore the intricate interdependent relationship among counting problems, considered from three frameworks for such problems: Holant Problems, counting CSP and weighted H-colorings. We consider these problems for general complex valued functions
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::540012112b4822814228dff8c46a821e