English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  Generating Randomized Roundings with Cardinality Constraints and Derandomizations

Doerr, B. (2006). Generating Randomized Roundings with Cardinality Constraints and Derandomizations. In STACS 2006, 23rd Annual Symposium on Theoretical Aspects of Computer Science (pp. 571-583). Berlin, Germany: Springer.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-22F7-0 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-22FA-A
Genre: Conference Paper

Files

show Files
hide Files
:
DoerrStacs2006.pdf (Any fulltext), 448KB
 
File Permalink:
-
Name:
DoerrStacs2006.pdf
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Doerr, Benjamin1, Author           
Durand, Bruno, Editor
Thomas, Wolfgang, Editor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: We provide a general method to generate randomized roundings that satisfy cardinality constraints. Our approach is different from the one taken by Srinivasan (FOCS 2001) and Gandhi et al. (FOCS 2002) for one global constraint and the bipartite edge weight rounding problem. Also for these special cases, our approach is the first that can be derandomized. For the bipartite edge weight rounding problem, in addition, we gain an factor run-time improvement for generating the randomized solution. We also improve the current best result on the general problem of derandomizing randomized roundings. Here we obtain a simple O(mnlog n) time algorithm that works in the RAM model for arbitrary matrices with entries in . This improves over the O(mn2 log(mn)) time solution of Srivastav and Stangier.

Details

show
hide
Language(s): eng - English
 Dates: 2007-04-262006
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 314403
Other: Local-ID: C1256428004B93B8-482118BCAB9812F7C125727A004F8EA3-DoerrStacs2006
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Marseille, France
Start-/End Date: 2006-02-23

Legal Case

show

Project information

show

Source 1

show
hide
Title: STACS 2006, 23rd Annual Symposium on Theoretical Aspects of Computer Science
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Berlin, Germany : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 571 - 583 Identifier: ISBN: 3-540-32301-5

Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 3884 Sequence Number: - Start / End Page: - Identifier: -