@article{11759,
  abstract     = {Matching markets play a prominent role in economic theory. A prime example of such a market is the sponsored search market. Here, as in other markets of that kind, market equilibria correspond to feasible, envy free, and bidder optimal outcomes. For settings without budgets such an outcome always exists and can be computed in polynomial-time by the so-called Hungarian Method. Moreover, every mechanism that computes such an outcome is incentive compatible. We show that the Hungarian Method can be modified so that it finds a feasible, envy free, and bidder optimal outcome for settings with budgets. We also show that in settings with budgets no mechanism that computes such an outcome can be incentive compatible for all inputs. For inputs in general position, however, the presented mechanism—as any other mechanism that computes such an outcome for settings with budgets—is incentive compatible.},
  author       = {Dütting, Paul and Henzinger, Monika H and Weber, Ingmar},
  issn         = {0020-0190},
  journal      = {Information Processing Letters},
  number       = {3},
  pages        = {67--73},
  publisher    = {Elsevier},
  title        = {{Sponsored search, market equilibria, and the Hungarian Method}},
  doi          = {10.1016/j.ipl.2012.11.006},
  volume       = {113},
  year         = {2013},
}

@article{11760,
  abstract     = {We study a novel load balancing problem that arises in web search engines. The problem is a combination of an offline assignment problem, where files need to be (copied and) assigned to machines, and an online load balancing problem, where requests ask for specific files and need to be assigned to a corresponding machine, whose load is increased
by this. We present simple deterministic algorithms for this problem and exhibit an interesting trade-off between the available space to make file copies and the obtainable makespan. We also give non-trivial lower bounds for a large class of deterministic algorithms and present a randomized algorithm that beats these bounds with high probability.},
  author       = {Dütting, Paul and Henzinger, Monika H and Weber, Ingmar},
  issn         = {0020-0190},
  journal      = {Information Processing Letters},
  number       = {4},
  pages        = {178--183},
  publisher    = {Elsevier},
  title        = {{Offline file assignments for online load balancing}},
  doi          = {10.1016/j.ipl.2010.11.022},
  volume       = {111},
  year         = {2011},
}

@article{11761,
  abstract     = {We prove that in an undirected graph there are at most O(n²) cuts of size strictly less than of the size of the minimum cut.},
  author       = {Henzinger, Monika H and Williamson, David P.},
  issn         = {0020-0190},
  journal      = {Information Processing Letters},
  number       = {1},
  pages        = {41--44},
  publisher    = {Elsevier},
  title        = {{On the number of small cuts in a graph}},
  doi          = {10.1016/0020-0190(96)00079-8},
  volume       = {59},
  year         = {1996},
}

@article{4048,
  abstract     = {Given a sequence of n points that form the vertices of a simple polygon, we show that determining a closest pair requires OMEGA(n log n) time in the algebraic decision tree model. Together with the well-known O(n log n) upper bound for finding a closest pair, this settles an open problem of Lee and Preparata. We also extend this O(n log n) upper bound to the following problem: Given a collection of sets with a total of n points in the plane, find for each point a closest neighbor that does not belong to the same set.},
  author       = {Aggarwal, Alok and Edelsbrunner, Herbert and Raghavan, Prabhakar and Tiwari, Prasoon},
  issn         = {1872-6119},
  journal      = {Information Processing Letters},
  number       = {1},
  pages        = {55 -- 60},
  publisher    = {Elsevier},
  title        = {{Optimal time bounds for some proximity problems in the plane}},
  doi          = {10.1016/0020-0190(92)90133-G},
  volume       = {42},
  year         = {1992},
}

@article{4517,
  abstract     = {It has been observed repeatedly that the standard safety-liveness classification for properties of reactive systems does not fit for real-time properties. This is because the implicit “liveliness” of time shifts the spectrum towards the safety side. While, for example, response—that “something good” will happen eventually—is a classical liveness property, bounded response—that “something good” will happen soon, within a certain amount of time—has many characteristics of safety. We account for this phenomenon formally by defining safety and liveness relative to a given condition, such as the progress of time.},
  author       = {Henzinger, Thomas A},
  issn         = {0020-0190},
  journal      = {Information Processing Letters},
  number       = {3},
  pages        = {135 -- 141},
  publisher    = {Elsevier},
  title        = {{Sooner Is Safer Than Later}},
  doi          = {10.1016/0020-0190(92)90005-G},
  volume       = {43},
  year         = {1992},
}

@article{4094,
  abstract     = {The visibility graph of a finite set of line segments in the plane connects two endpoints u and v if and only if the straight line connection between u and v does not cross any line segment of the set. This article proves that 5n - 4 is a lower bound on the number of edges in the visibility graph of n nonintersecting line segments in the plane. This bound is tight.},
  author       = {Edelsbrunner, Herbert and Shen, Xiaojun},
  issn         = {1872-6119},
  journal      = {Information Processing Letters},
  number       = {2},
  pages        = {61 -- 64},
  publisher    = {Elsevier},
  title        = {{A tight lower bound on the size of visibility graphs}},
  doi          = {10.1016/0020-0190(87)90038-X},
  volume       = {26},
  year         = {1987},
}

@article{4101,
  abstract     = {In a number of recent papers, techniques from computational geometry (the field of algorithm design that deals with objects in multi-dimensional space) have been applied to some problems in the area of computer graphics. In this way, efficient solutions were obtained for the windowing problem that asks for those line segments in a planar set that lie in given window (range) and the moving problem that asks for the first line segment that comes into the window when moving the window in some direction. In this paper we show that also the zooming problem, which asks for the first line segment that comes into the window when we enlarge it, can be solved efficiently. This is done by repeatedly performing range queries with ranges of varying sizes. The obtained structure is dynamic and yields a query time of O(log2n) and an insertion and deletion time of O(log2n), where n is the number of line segments in the set. The amount of storage required is O(n log n). It is also shown that the technique of repeated range search can be used to solve several other problems efficiently.},
  author       = {Edelsbrunner, Herbert and Overmars, Mark},
  issn         = {1872-6119},
  journal      = {Information Processing Letters},
  number       = {6},
  pages        = {413 -- 417},
  publisher    = {Elsevier},
  title        = {{Zooming by repeated range detection}},
  doi          = {10.1016/0020-0190(87)90120-7},
  volume       = {24},
  year         = {1987},
}

@article{4099,
  abstract     = {Let S denote a set of n points in the Euclidean plane. A halfplanar range query specifies a halfplane h and requires the determination of the number of points in S which are contained in h. A new data structure is described which stores S in O(n) space and allows us to answer a halfplanar range query in O(nlog2(1+√5)−1) time in the worst case, thus improving the best result known before. The structure can be built in O(n log n) time.},
  author       = {Edelsbrunner, Herbert and Welzl, Emo},
  issn         = {1872-6119},
  journal      = {Information Processing Letters},
  number       = {5},
  pages        = {289 -- 293},
  publisher    = {Elsevier},
  title        = {{Halfplanar range search in linear space and O(n0.695) query time}},
  doi          = {10.1016/0020-0190(86)90088-8},
  volume       = {23},
  year         = {1986},
}

@article{4111,
  abstract     = {This paper describes an optimal solution for the following geometric search problem defined for a set P of n points in three dimensions: Given a plane h with all points of P on one side and a line ℓ in h, determine a point of P that is hit first when h is rotated around ℓ. The solution takes O(n) space and O(log n) time for a query. By use of geometric transforms, the post-office problem for a finite set of points in two dimensions and certain two-dimensional point location problems are reduced to the former problem and thus also optimally solved.},
  author       = {Edelsbrunner, Herbert and Maurer, Hermann},
  issn         = {1872-6119},
  journal      = {Information Processing Letters},
  number       = {1},
  pages        = {39 -- 47},
  publisher    = {Elsevier},
  title        = {{Finding extreme-points in 3-dimensions and solving the post-office problem in the plane}},
  doi          = {10.1016/0020-0190(85)90107-3},
  volume       = {21},
  year         = {1985},
}

@article{4130,
  author       = {Edelsbrunner, Herbert and Maurer, Hermann and Kirkpatrick, David},
  issn         = {1872-6119},
  journal      = {Information Processing Letters},
  number       = {2},
  pages        = {74 -- 79},
  publisher    = {Elsevier},
  title        = {{Polygonal intersection searching}},
  doi          = {10.1016/0020-0190(82)90090-4},
  volume       = {14},
  year         = {1982},
}

@article{4132,
  author       = {Edelsbrunner, Herbert and Maurer, Hermann},
  issn         = {0020-0190},
  journal      = {Information Processing Letters},
  number       = {4-5},
  pages        = {177 -- 181},
  publisher    = {Elsevier},
  title        = {{On the intersection of Orthogonal objects}},
  doi          = {10.1016/0020-0190(81)90053-3},
  volume       = {13},
  year         = {1981},
}