2 Search Results for "Kumar, Ananya"

Document
DOI: 10.4230/LIPIcs.ICALP.2018.21
Approximate Convex Hull of Data Streams

Authors: Avrim Blum, Vladimir Braverman, Ananya Kumar, Harry Lang, and Lin F. Yang

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
Given a finite set of points P subseteq R^d, we would like to find a small subset S subseteq P such that the convex hull of S approximately contains P. More formally, every point in P is within distance epsilon from the convex hull of S. Such a subset S is called an epsilon-hull. Computing an epsilon-hull is an important problem in computational geometry, machine learning, and approximation algorithms. In many applications, the set P is too large to fit in memory. We consider the streaming model where the algorithm receives the points of P sequentially and strives to use a minimal amount of memory. Existing streaming algorithms for computing an epsilon-hull require O(epsilon^{(1-d)/2}) space, which is optimal for a worst-case input. However, this ignores the structure of the data. The minimal size of an epsilon-hull of P, which we denote by OPT, can be much smaller. A natural question is whether a streaming algorithm can compute an epsilon-hull using only O(OPT) space. We begin with lower bounds that show, under a reasonable streaming model, that it is not possible to have a single-pass streaming algorithm that computes an epsilon-hull with O(OPT) space. We instead propose three relaxations of the problem for which we can compute epsilon-hulls using space near-linear to the optimal size. Our first algorithm for points in R^2 that arrive in random-order uses O(log n * OPT) space. Our second algorithm for points in R^2 makes O(log(epsilon^{-1})) passes before outputting the epsilon-hull and requires O(OPT) space. Our third algorithm, for points in R^d for any fixed dimension d, outputs, with high probability, an epsilon-hull for all but delta-fraction of directions and requires O(OPT * log OPT) space.
Cite as

Avrim Blum, Vladimir Braverman, Ananya Kumar, Harry Lang, and Lin F. Yang. Approximate Convex Hull of Data Streams. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 21:1-21:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{blum_et_al:LIPIcs.ICALP.2018.21,
  author =	{Blum, Avrim and Braverman, Vladimir and Kumar, Ananya and Lang, Harry and Yang, Lin F.},
  title =	{{Approximate Convex Hull of Data Streams}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{21:1--21:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.21},
  URN =		{urn:nbn:de:0030-drops-90254},
  doi =		{10.4230/LIPIcs.ICALP.2018.21},
  annote =	{Keywords: Convex Hulls, Streaming Algorithms, Epsilon Kernels, Sparse Coding}
}
Document
DOI: 10.4230/DagSemProc.04461.18
Optimizing Surface Profiles during Hot Rolling: A Genetic Algorithms based Multi-objective Analysis

Authors: Nirupam Chakraborti, Barrenkala Siva Kumar, Satish V. Babu, Sri Subhrangshu Moitra, and Ananya Mukhopadhyay

Published in: Dagstuhl Seminar Proceedings, Volume 4461, Practical Approaches to Multi-Objective Optimization (2005)

Abstract
A hot rolled strip produced by any integrated steel plant would require satisfying some stringent requirements of its surface profile. Crown and Flatness are two industrially accepted quantifiers that relate to the geometric tolerances in the rolled strips. This study attempts to regulate both crown and flatness within an acceptable limit, satisfying more than one objective at a time. Mathematically, this leads to a multi-objective optimization problem where the solution is no longer unique and a family of equally feasible solutions leads to the so called Pareto-Front, where each member is simply as good as the others. To implement this concept in the present context, one needs to realize that the surface deformation, which is ultimately imparted to the rolled sheets, comes from more than one source. The wear of the rolls, their thermal expansion, bending, and also deformation, contribute significantly towards the crown and flatness that is ultimately observed. During this study a detailed mathematical model has been worked out for this process incorporating all of these phenomena. Computation for the Pareto-optimality has been carried out using different forms of biologically inspired Genetic Algorithms, often integrated with an Ant Colony Optimization Scheme. Ultimately the model has been fine tuned for the hot rolling practice in a major integrated steel plant and tested against their actual operational data.
Cite as

Nirupam Chakraborti, Barrenkala Siva Kumar, Satish V. Babu, Sri Subhrangshu Moitra, and Ananya Mukhopadhyay. Optimizing Surface Profiles during Hot Rolling: A Genetic Algorithms based Multi-objective Analysis. In Practical Approaches to Multi-Objective Optimization. Dagstuhl Seminar Proceedings, Volume 4461, pp. 1-12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{chakraborti_et_al:DagSemProc.04461.18,
  author =	{Chakraborti, Nirupam and Kumar, Barrenkala Siva and Babu, Satish V. and Moitra, Sri Subhrangshu and Mukhopadhyay, Ananya},
  title =	{{Optimizing Surface Profiles during Hot Rolling: A Genetic Algorithms based Multi-objective Analysis}},
  booktitle =	{Practical Approaches to Multi-Objective Optimization},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4461},
  editor =	{J\"{u}rgen Branke and Kalyanmoy Deb and Kaisa Miettinen and Ralph E. Steuer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04461.18},
  URN =		{urn:nbn:de:0030-drops-2454},
  doi =		{10.4230/DagSemProc.04461.18},
  annote =	{Keywords: Rolling, Hot Rolling, Crown, Flatness, Genetic Algorithms, Ant Colony Optimization, Multi-objective Optimization, Pareto Front, Multi-objective Evolut}
}
  • Refine by Author
  • 1 Babu, Satish V.
  • 1 Blum, Avrim
  • 1 Braverman, Vladimir
  • 1 Chakraborti, Nirupam
  • 1 Kumar, Ananya
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Sketching and sampling
  • 1 Theory of computation → Streaming models

  • Refine by Keyword
  • 1 Ant Colony Optimization
  • 1 Convex Hulls
  • 1 Crown
  • 1 Epsilon Kernels
  • 1 Flatness
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2005
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact