NDLI: Improved approximation results for stochastic knapsack problems

Please wait, while we are loading the content...

Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with sub-constant error

The streaming complexity of cycle counting, sorting by reversals, and other problems

Streaming k-means on well-clusterable data

Efficient sketches for the set query problem

Exponential time improvement for min-wise based algorithms

A simple and fast 2-approximation algorithm for the one-warehouse multi-retailers problem

Generalized machine activation problems

An online scalable algorithm for minimizing $l_{k}-norms$ of weighted flow time on unrelated machines

Online scalable scheduling for the $l_{k}-norms$ of flow time without conservation of work

Online scheduling on identical machines using SRPT

A complete resolution of the Keller maximum clique problem

On independent sets in random graphs

Coloring random graphs online without creating monochromatic subgraphs

The maximum size of a Sidon set contained in a sparse random set of integers

On Buffon machines and numbers

Graph coloring via the probabilistic method

An almost optimal unrestricted fast Johnson-Lindenstrauss transform

A Stackelberg strategy for routing flow over time

A subexponential lower bound for the random facet algorithm for parity games

On minmax theorems for multiplayer games

Near-optimal no-regret algorithms for zero-sum games

Local smoothness and the price of anarchy in atomic splittable congestion games

I/O-efficient contour queries on terrains

Implicit flow routing on terrains with applications to surface networks and drainage structures

Shortest non-crossing walks in the plane

Computing shortest paths amid pseudodisks

On the complexity of time-dependent shortest paths

A master theorem for discrete divide and conquer recurrences

Optimal pattern matching in LZW compressed strings

Random access to grammar-compressed strings

Ordered and unordered top-K range reporting in large data sets

Top-K color queries for document retrieval

Mobile geometric graphs: detection, coverage and percolation

Randomized diffusion for indivisible loads

Fast information spreading in graphs with large weak conductance

On the randomness requirements of rumor spreading

Rumor spreading and vertex expansion on regular graphs

Bin packing via discrepancy of permutations

Algorithms and hardness for subspace approximation

Approximating matrix p-norms

Subsampling mathematical relaxations and average-case complexity

Towards an SDP-based approach to spectral methods: a nearly-linear-time algorithm for graph partitioning and decomposition

Faster quantum algorithm for evaluating game trees

Reflections for quantum query algorithms

Temperature 1 self-assembly: deterministic assembly in 3D and probabilistic assembly in 2D

The power of nondeterminism in self-assembly

Algorithms for implicit hitting set problems

An algorithmic decomposition of claw-free graphs leading to an $O(n^{3})-algorithm$ for the weighted stable set problem

Randomized greedy: new variants of some classic approximation algorithms

Randomized variants of Johnson's algorithm for MAX SAT

The local lemma is tight for SAT

Pricing on paths: a PTAS for the highway problem

On the approximability of budget feasible mechanisms

Welfare guarantees for combinatorial auctions with item bidding

Mechanism design via correlation gap

Bayesian incentive compatibility via fractional assignments

Bayesian incentive compatibility via matchings

Bidimensionality and EPTAS

Slightly superexponential parameterized problems

Known algorithms on graphs of bounded treewidth are probably optimal

Continuous local search

Range selection and median: tight cell probe lower bounds and adaptive data structures

Where computer vision needs help from computer science

An optimal-time construction of sparse Euclidean spanners with tiny diameter

Fast, precise and dynamic distance queries

Approximate nearest neighbor search for low dimensional queries

Dimensionality reduction: beyond the Johnson-Lindenstrauss bound

A nonlinear approach to dimension reduction

Hitting time results for Maker-Breaker games: extended abstract

Packing tight Hamilton cycles in 3-uniform hypergraphs

Networks of random cycles

Phase transition for Glauber dynamics for independent sets on regular trees

On belief propagation guided decimation for random k-SAT

The asymmetric traveling salesman problem on graphs with bounded genus

Capacitated Metric Labeling

Multicommodity facility location under group Steiner access cost

Survivable network design problems in wireless networks

Prize-collecting Steiner problems on planar graphs

On graph crossing number and edge planarization

Ranking with submodular valuations

Multi-budgeted matchings and matroid intersection via dependent rounding

Submodular maximization by simulated annealing

The matroid median problem

Persistent predecessor search and orthogonal point location on the word RAM

New approximation algorithms for minimum enclosing convex shapes

Computing the independence number of intersection graphs

Minimum cuts and shortest non-separating cycles via homology covers

Embedding stacked polytopes on a polynomial-size grid

Overlap properties of geometric expanders: extended abstract

On the degree distribution of random planar graphs

Component structure of the vacant set induced by a random walk on a random graph

The multiple-orientability thresholds for random hypergraphs

The rigidity transition in random graphs

Online vertex-weighted bipartite matching and single-bid budgeted allocations

Secretary problems: laminar matroid and interval scheduling

Matroid secretary problem in the random assignment model

Online stochastic matching: online actions based on offline statistics

An optimal lower bound for buffer management in multi-queue switches

An intersection model for multitolerance graphs: efficient algorithms and hierarchy

Faster and dynamic algorithms for maximal end-component decomposition and related graph problems in probabilistic verification

Faster replacement paths

Computing replacement paths in surface embedded graphs

Improved dynamic algorithms for maintaining approximate shortest paths under deletions

Algebraic algorithms for linear matroid parity problems

On parity check (0, 1)-matrix over $Z_{p}$

Code equivalence and group isomorphism

Efficient algorithms for some special cases of the polynomial equivalence problem

Low rank matrix-valued chernoff bounds and approximate matrix multiplication

Computational geometry for non-geometers: recent developments on some classical problems

Improved deterministic algorithms for decremental transitive closure and strongly connected components

Approximating the girth

Approximating the statistics of various properties in randomly weighted graphs

Counting and detecting small subgraphs via equations and matrix multiplication

On succinct convex greedy drawing of 3-connected plane graphs

Distributed selfish load balancing on networks

On the complexity of approximating a Nash equilibrium

Fast convergence of natural bargaining dynamics in exchange networks

Wireless capacity with oblivious power in general metrics

A constant-factor approximation for wireless capacity maximization with power control in the SINR model

On LP-based approximability for strict CSPs

Tight bounds on the approximability of almost-satisfiable Horn SAT and exact hitting set

Hardness results for agnostically learning low-degree polynomial threshold functions

Tight hardness results for minimizing discrepancy

The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number

Risk-averse stochastic optimization: probabilistically-constrained models and algorithms for black-box distributions

Improved approximation results for stochastic knapsack problems

The stubborn problem is stubborn no more: a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem

Approximate dynamic programming using halfspace queries and multiscale Monge decomposition

Nearly tight bounds for testing function isomorphism

The dichotomy of list homomorphisms for digraphs

Dichotomy for Holant problems of Boolean domain

Bounding the randomized decision tree complexity of read-once Boolean functions

Improved space bounds for cache-oblivious range reporting

Triangulating the square and squaring the triangle: quadtrees and Delaunay triangulations are equivalent

Improved bound for the union of fat triangles

Improved approximation results for stochastic knapsack problems

Content Provider	ACM Digital Library
Author	Bhalgat, Anand Goel, Ashish Khanna, Sanjeev
Abstract	In the stochastic knapsack problem, we are given a set of items each associated with a probability distribution on sizes and a profit, and a knapsack of unit capacity. The size of an item is revealed as soon as it is inserted into the knapsack, and the goal is to design a policy that maximizes the expected profit of items that are successfully inserted into the knapsack. The stochastic knapsack problem is a natural generalization of the classical knapsack problem, and arises in many applications, including bandwidth allocation, budgeted learning, and scheduling. An adaptive policy for stochastic knapsack specifies the next item to be inserted based on observed sizes of the items inserted thus far. The adaptive policy can have an exponentially large explicit description and is known to be PSPACE-hard to compute. The best known approximation for this problem is a (3 + ε)-approximation for any ε > 0. Our first main result is a relaxed PTAS (Polynomial Time Approximation Scheme) for the adaptive policy, that is, for any ε > 0, we present a poly-time computable (1 + ε)-approximate adaptive policy when knapsack capacity is relaxed to 1+ε. At a high-level, the proof is based on transforming an arbitrary collection of item size distributions to canonical item size distributions that admit a compact description. We then establish a coupling that shows a (1 + ε)-approximation can be achieved for the original problem by a canonical policy that makes decisions at each step by observing events drawn from the sample space of canonical size distributions. Finally, we give a mechanism for approximating the optimal canonical policy. Our second main result is an (8/3 + ε)-approximate adaptive policy for any ε > 0 without relaxing the knapsack capacity, improving the earlier (3 + ε)-approximation result. Interestingly, we obtain this result by using the PTAS described above. We establish an existential result that the optimal policy for the knapsack with capacity 1 can be folded to get a policy with expected profit 3OPT/8 for a knapsack with capacity (1 ™ ε), with capacity relaxed to 1 only for the first item inserted. We then use our PTAS result to compute the (1 + ε)-approximation to such policy. Our techniques also yield a relaxed PTAS for non-adaptive policies. Finally, we also show that our ideas can be extended to yield improved approximation guarantees for multi-dimensional and fixed set variants of the stochastic knapsack problem.
Starting Page	1647
Ending Page	1665
Page Count	19
File Format	PDF
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2011-01-23
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in