---
_id: '11903'
abstract:
- lang: eng
  text: "Online social networks allow the collection of large amounts of data about
    the influence between users connected by a friendship-like relationship. When
    distributing items among agents forming a social network, this information allows
    us to exploit network externalities that each agent receives from his neighbors
    that get the same item. In this paper we consider Friends-of-Friends (2-hop) network
    externalities, i.e., externalities that not only depend on the neighbors that
    get the same item but also on neighbors of neighbors. For these externalities
    we study a setting where multiple different items are assigned to unit-demand
    agents. Specifically, we study the problem of welfare maximization under different
    types of externality functions. Let n be the number of agents and m be the number
    of items. Our contributions are the following: (1) We show that welfare maximization
    is APX-hard; we show that even for step functions with 2-hop (and also with 1-hop)
    externalities it is NP-hard to approximate social welfare better than (1−1/e).
    (2) On the positive side we present (i) an \U0001D442(\U0001D45B√)-approximation
    algorithm for general concave externality functions, (ii) an O(log m)-approximation
    algorithm for linear externality functions, and (iii) a 518(1−1/\U0001D452)-approximation
    algorithm for 2-hop step function externalities. We also improve the result from
    [7] for 1-hop step function externalities by giving a 12(1−1/\U0001D452)-approximation
    algorithm."
article_processing_charge: No
article_type: original
author:
- first_name: Sayan
  full_name: Bhattacharya, Sayan
  last_name: Bhattacharya
- first_name: Wolfgang
  full_name: Dvořák, Wolfgang
  last_name: Dvořák
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Martin
  full_name: Starnberger, Martin
  last_name: Starnberger
citation:
  ama: Bhattacharya S, Dvořák W, Henzinger M, Starnberger M. Welfare maximization
    with friends-of-friends network externalities. <i>Theory of Computing Systems</i>.
    2017;61(4):948-986. doi:<a href="https://doi.org/10.1007/s00224-017-9759-8">10.1007/s00224-017-9759-8</a>
  apa: Bhattacharya, S., Dvořák, W., Henzinger, M., &#38; Starnberger, M. (2017).
    Welfare maximization with friends-of-friends network externalities. <i>Theory
    of Computing Systems</i>. Springer Nature. <a href="https://doi.org/10.1007/s00224-017-9759-8">https://doi.org/10.1007/s00224-017-9759-8</a>
  chicago: Bhattacharya, Sayan, Wolfgang Dvořák, Monika Henzinger, and Martin Starnberger.
    “Welfare Maximization with Friends-of-Friends Network Externalities.” <i>Theory
    of Computing Systems</i>. Springer Nature, 2017. <a href="https://doi.org/10.1007/s00224-017-9759-8">https://doi.org/10.1007/s00224-017-9759-8</a>.
  ieee: S. Bhattacharya, W. Dvořák, M. Henzinger, and M. Starnberger, “Welfare maximization
    with friends-of-friends network externalities,” <i>Theory of Computing Systems</i>,
    vol. 61, no. 4. Springer Nature, pp. 948–986, 2017.
  ista: Bhattacharya S, Dvořák W, Henzinger M, Starnberger M. 2017. Welfare maximization
    with friends-of-friends network externalities. Theory of Computing Systems. 61(4),
    948–986.
  mla: Bhattacharya, Sayan, et al. “Welfare Maximization with Friends-of-Friends Network
    Externalities.” <i>Theory of Computing Systems</i>, vol. 61, no. 4, Springer Nature,
    2017, pp. 948–86, doi:<a href="https://doi.org/10.1007/s00224-017-9759-8">10.1007/s00224-017-9759-8</a>.
  short: S. Bhattacharya, W. Dvořák, M. Henzinger, M. Starnberger, Theory of Computing
    Systems 61 (2017) 948–986.
date_created: 2022-08-17T11:14:12Z
date_published: 2017-11-01T00:00:00Z
date_updated: 2024-11-06T12:24:23Z
day: '01'
doi: 10.1007/s00224-017-9759-8
extern: '1'
fulldoi: https://doi.org/10.1007/s00224-017-9759-8
intvolume: '        61'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.1007/s00224-017-9759-8
month: '11'
oa: 1
oa_version: Published Version
page: 948-986
publication: Theory of Computing Systems
publication_identifier:
  eissn:
  - 1433-0490
  issn:
  - 1432-4350
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
  record:
  - id: '11837'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Welfare maximization with friends-of-friends network externalities
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 61
year: '2017'
...
---
OA_type: closed access
_id: '2427'
abstract:
- lang: eng
  text: Intersection graphs of disks and of line segments, respectively, have been
    well studied, because of both practical applications and theoretically interesting
    properties of these graphs. Despite partial results, the complexity status of
    the Clique problem for these two graph classes is still open. Here, we consider
    the Clique problem for intersection graphs of ellipses, which, in a sense, interpolate
    between disks and line segments, and show that the problem is APX-hard in that
    case. Moreover, this holds even if for all ellipses, the ratio of the larger over
    the smaller radius is some prescribed number. Furthermore, the reduction immediately
    carries over to intersection graphs of triangles. To our knowledge, this is the
    first hardness result for the Clique problem in intersection graphs of convex
    objects with finite description complexity. We also describe a simple approximation
    algorithm for the case of ellipses for which the ratio of radii is bounded.
article_processing_charge: No
article_type: original
author:
- first_name: Christoph
  full_name: Ambühl, Christoph
  last_name: Ambühl
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
citation:
  ama: Ambühl C, Wagner U. The Clique problem in intersection graphs of ellipses and
    triangles. <i>Theory of Computing Systems</i>. 2005;38(3):279-292. doi:<a href="https://doi.org/10.1007/s00224-005-1141-6">10.1007/s00224-005-1141-6</a>
  apa: Ambühl, C., &#38; Wagner, U. (2005). The Clique problem in intersection graphs
    of ellipses and triangles. <i>Theory of Computing Systems</i>. Springer Nature.
    <a href="https://doi.org/10.1007/s00224-005-1141-6">https://doi.org/10.1007/s00224-005-1141-6</a>
  chicago: Ambühl, Christoph, and Uli Wagner. “The Clique Problem in Intersection
    Graphs of Ellipses and Triangles.” <i>Theory of Computing Systems</i>. Springer
    Nature, 2005. <a href="https://doi.org/10.1007/s00224-005-1141-6">https://doi.org/10.1007/s00224-005-1141-6</a>.
  ieee: C. Ambühl and U. Wagner, “The Clique problem in intersection graphs of ellipses
    and triangles,” <i>Theory of Computing Systems</i>, vol. 38, no. 3. Springer Nature,
    pp. 279–292, 2005.
  ista: Ambühl C, Wagner U. 2005. The Clique problem in intersection graphs of ellipses
    and triangles. Theory of Computing Systems. 38(3), 279–292.
  mla: Ambühl, Christoph, and Uli Wagner. “The Clique Problem in Intersection Graphs
    of Ellipses and Triangles.” <i>Theory of Computing Systems</i>, vol. 38, no. 3,
    Springer Nature, 2005, pp. 279–92, doi:<a href="https://doi.org/10.1007/s00224-005-1141-6">10.1007/s00224-005-1141-6</a>.
  short: C. Ambühl, U. Wagner, Theory of Computing Systems 38 (2005) 279–292.
date_created: 2018-12-11T11:57:36Z
date_published: 2005-05-01T00:00:00Z
date_updated: 2026-08-07T09:00:14Z
day: '01'
doi: 10.1007/s00224-005-1141-6
extern: '1'
fulldoi: https://doi.org/10.1007/s00224-005-1141-6
intvolume: '        38'
issue: '3'
language:
- iso: eng
month: '05'
oa_version: None
page: 279 - 292
publication: Theory of Computing Systems
publication_identifier:
  eissn:
  - 1433-0490
  issn:
  - 1432-4350
publication_status: published
publisher: Springer Nature
publist_id: '4497'
status: public
title: The Clique problem in intersection graphs of ellipses and triangles
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 38
year: '2005'
...